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

140
Глава 5.
Генетические алгоритмы
Рис. 5.1.
Обобщенная схема генетического алгоритма
Листинг 5.2. 
GeneticAlgorithm.java
package 
chapter5;
import 
java.util.ArrayList;
import 
java.util.Collections;
import 
java.util.List;
import 
java.util.Random;
public class 
GeneticAlgorithmextends 
Chromosome> {
public enum 
SelectionType {
ROULETTE
, 
TOURNAMENT
;
}
GeneticAlgorithm
.принимает.параметризованный.тип,.который.соответствует.
Chromosome
.и.называется.
C
..Перечисление.
SelectionType
.является.внутренним.
типом,.используемым.для.определения.метода.отбора,.применяемого.в.алгоритме..
Существует.два.наиболее.распространенных.метода.отбора.для.генетического.
алгоритма.—.
отбор
.
методом
.
рулетки
.(иногда.называемый.
пропорциональным
.
от-
бором
.
по
.
жизнеспособности
).и.
турнирный
.
отбор
..Первый.дает.каждой.хромосоме.

---

5.2. Обобщенный генетический алгоритм
141
шанс.быть.отобранной.пропорционально.ее.жизнеспособности..При.турнирном.
отборе.определенное.количество.случайно.выбранных.хромосом.борются.друг.
с.другом.и.выбираются.обладающие.лучшей.жизнеспособностью.(листинг.5.3).
Листинг 5.3. 
GeneticAlgorithm.java (продолжение)
private 
ArrayList population;
private double 
mutationChance;
private double 
crossoverChance;
private 
SelectionType selectionType;
private 
Random random;
public 
GeneticAlgorithm(List initialPopulation, 
double 
mutationChance,
double 
crossoverChance, SelectionType selectionType) {
this
.population = 
new 
ArrayList<>(initialPopulation);
this
.mutationChance = mutationChance;
this
.crossoverChance = crossoverChance;
this
.selectionType = selectionType;
this
.random = 
new 
Random();
}
В.приведенном.коде.представлены.некоторые.свойства.генетического.алгоритма,.
которые.будут.настроены.в.момент.создания.посредством.
initialPopulation
.—.
хромосомы.первого.поколения.алгоритма..
mutationChance
.—.это.вероятность.
мутации.каждой.хромосомы.в.каждом.поколении..
crossoverChance
.—.вероятность.
того,.что.у.двух.родителей,.отобранных.для.размножения,.появятся.потомки,.
представляющие.собой.смесь.родительских.генов,.в.противном.случае.они.будут.
просто.дубликатами.родителей..Наконец,.
selectionType
.—.это.тип.метода.отбора,.
описанный.в.перечислении.
SelectionType
.
В.наших.примерах.
population
.инициализируется.случайным.набором.хромосом..
Другими.словами,.первое.поколение.хромосом.состоит.из.случайных.особей..Это.
точка.потенциальной.оптимизации.для.более.сложного.генетического.алгоритма..
Вместо.того.чтобы.начинать.с.чисто.случайных.особей,.благодаря.некоторому.
знанию.конкретной.задачи.можно.взять.первое.поколение,.содержащее.особей,.
находящихся.ближе.к.решению..Это.называется.
посевом
.
Теперь.рассмотрим.два.метода.отбора,.которые.поддерживает.наш.класс.(ли-
стинг.5.4).
Листинг 5.4. 
GeneticAlgorithm.java (продолжение)
// используем метод рулетки чтобы выбрать родителей