Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

150
Глава 5.
Генетические алгоритмы
import 
java.util.Random;
public class 
SendMoreMoney2 
extends 
Chromosome {
private 
List letters;
private 
Random random;
public 
SendMoreMoney2(List letters) {
this
.letters = letters;
random = 
new 
Random();
}
public static 
SendMoreMoney2 randomInstance() {
List letters = 
new 
ArrayList<>(
List.
of
('S', 'E', 'N', 'D', 'M', 'O', 'R', 'Y', ' ', ' '));
Collections.
shuffle
(letters);
return new 
SendMoreMoney2(letters);
}
@Override
public double 
fitness() {
int 
s = letters.indexOf('S');
int 
e = letters.indexOf('E');
int 
n = letters.indexOf('N');
int 
d = letters.indexOf('D');
int 
m = letters.indexOf('M');
int 
o = letters.indexOf('O');
int 
r = letters.indexOf('R');
int 
y = letters.indexOf('Y');
int 
send = s * 1000 + e * 100 + n * 10 + d;
int 
more = m * 1000 + o * 100 + r * 10 + e;
int 
money = m * 10000 + o * 1000 + n * 100 + e * 10 + y;
int 
difference = Math.
abs
(money — (send + more));
 
return 
1.0 / (difference + 1.0);
}
@Override
public 
List crossover(SendMoreMoney2 other) {
SendMoreMoney2 child1 = 
new 
SendMoreMoney2(
new 
ArrayList<>(letters));
SendMoreMoney2 child2 = 
new 
SendMoreMoney2(
new 
ArrayList<>
(other.letters));
int 
idx1 = random.nextInt(letters.size());
int 
idx2 = random.nextInt(other.letters.size());
Character l1 = letters.get(idx1);
Character l2 = other.letters.get(idx2);
int 
idx3 = letters.indexOf(l2);
int 
idx4 = other.letters.indexOf(l1);
Collections.
swap
(child1.letters, idx1, idx3);
Collections.
swap
(child2.letters, idx2, idx4);
return 
List.
of
(child1, child2);
}
@Override
public void 
mutate() {

---

5.4. SEND + MORE = MONEY, улучшенный вариант
151
int 
idx1 = random.nextInt(letters.size());
int 
idx2 = random.nextInt(letters.size());
Collections.
swap
(letters, idx1, idx2);
}
@Override
public 
SendMoreMoney2 copy() {
return new 
SendMoreMoney2(
new 
ArrayList<>(letters));
}
@Override
public 
String toString() {
int 
s = letters.indexOf('S');
int 
e = letters.indexOf('E');
int 
n = letters.indexOf('N');
int 
d = letters.indexOf('D');
int 
m = letters.indexOf('M');
int 
o = letters.indexOf('O');
int 
r = letters.indexOf('R');
int 
y = letters.indexOf('Y');
int 
send = s * 1000 + e * 100 + n * 10 + d;
int 
more = m * 1000 + o * 100 + r * 10 + e;
int 
money = m * 10000 + o * 1000 + n * 100 + e * 10 + y;
int 
difference = Math.
abs
(money — (send + more));
return 
(send + " + " + more + " = " + money + " Difference: " + 
difference);
}
Однако.существует.серьезное.различие.между.методом.
satisfied()
.из.главы.3.
и.методом.
fitness()
,.задействованным.в.данной.главе..Здесь.мы.возвращаем.
1/(difference
.
+
.
1)
..
difference
.—.это.абсолютное.значение.разности.между.
MONEY.и.SEND.+.MORE..Оно.показывает,.насколько.далека.данная.хромосома.
от.решения.задачи..Если.бы.мы.пытались.минимизировать.
fitness()
,.то.воз-
вращения.одного.лишь.значения.
difference
.было.бы.достаточно..Но.поскольку.
GeneticAlgorithm
.пытается.максимизировать.
fitness()
,.необходимо.вычислить.
обратное.значение,.чтобы.меньшие.значения.выглядели.как.большие,.и.поэтому.
мы.делим.1.на.
difference
..Для.того.чтобы.
difference(0)
.было.равно.не.
fitness(0)
,.
а.
fitness(1)
,.к.
difference
.сначала.прибавляется.1..В.табл..5.1.показано,.как.это.
работает.