Генетические алгоритмы - Пример

Найти максимум функции f(x)=x2  в диапазоне 0<x<31.

В качестве функции пригодности выступает сама функция, чем больше значение, чем больше ее значение, тем лучше пригодность хромосомы.

Установим размер популяции, равный четырем строкам. 

Таблица 11.1 – Начальная популяция и оценка пригодности

 

Начальная популяция

x

f(x)

Относительная пригодность, %

1

01101

13

169

14,4

2

11000

24

576

49,2

3

01000

8

64

5,5

4

10011

19

361

30,9

 

 

 

1170

100

 

Так как функция пригодности второй строки — лучшая, отбираем две копии второй строки и оставляем первую и четвертую строки в родительском пуле. Отбор партнеров производим случайным образом: партнером первой строки служит вторая, партнером четвертой — тоже вторая. Положение точек скрещивания также случайно и выбирается следующим образом: для пары из первой и второй строк точка скрещивания — после четвертого бита; для пары из второй четвертой строк — после второго бита. 

Таблица 11.2– Родительский пул и скрещивание 

Родительский пул

Парная строка

До скрещивания

После скрещивания

1

01101

2

0110[1]

1100

2

11000

1

1100[0]

11001

3

11000

4

11[000]

11011

4

10011

2

10[011]

10000

 Второе поколение без мутации приведено ниже.

 Таблица 11.3 – Второе поколение 

Начальная популяция

x

f(x)

Относительная пригодность, %

1

1100

12

144

8,2%

2

11001

25

625

35,6%

3

11011

27

729

41,6%

4

10000

16

256

14,6%

 

 

 

1754

100

 Видно, что третья строка является лучшей во втором поколении и значении x=27 достаточно близко к отыскиваемому максимуму. Очевидно, что через несколько шагов оптимальное решение будет найден даже без использования оператора мутации.