Правила разработки генетического алгоритма

Теория ГА пока недостаточно разработана, однако можно сформулировать основные правила их составления:

1. ГА целесообразно использовать, если пространство поиска содержит один или несколько экстремумов. Для поиска нескольких экстремумов ГА запускается несколько раз до получения нескольких устойчивых (повторяющихся) решений. Если же пространство поиска небольшое, то решение может быть найдено методом полного перебора, и можно быть уверенным, что наилучшее возможное решение найдено, тогда как ГА мог с большей вероятностью сойтись к локальному оптимуму, а не к глобально лучшему решению.

2. Структура данных генетического алгоритма состоит из одной или более хромосом (обычно из одной). Как правило, хромосома - это битовая строка. В принципе, ГА не ограничены бинарным представлением. Известны другие реализации, построенные исключительно на векторах вещественных чисел.

3. Хромосома состоит только из положительных двоичных чисел. При обработке с помощью ГА отрицательных чисел к ним нужно прибавить положительную константу, превращающую хромосому в неотрицательное число. После вычислений по ГА из результата вычитается эта константа. Например, если особь х_i изменяется в интервале от -3 до +5, то к ней прибавляется константа 3, которая переводит её в диапазон от 0 до 8.

4. Длина строки должна обеспечивать желаемую точность. Допустим, что 10-разрядное кодирование достаточно и для x₁, и для x₂. Тогда оптимизируемая структура данных - 20-битная строка, представляющая конкатенацию (слияние) кодировок x₁ и x₂. Переменная x₁ размещается в крайних левых 10-разрядах, тогда как x₂ размещается в правой части генотипа особи (20-битовой строки).

5. В ГА следует использовать шаблоны – строки с фиксированными генами, они уменьшают количество итераций (приближений, циклов) ГА.

6. Для оптимизации структуры данных с помощью ГА используется функция приспособленности. В функциональной максимизации целевая функция сама выступает в качестве функции приспособленности (например, наш двумерный пример); для задач минимизации целевую функцию следует инвертировать и сместить в область положительных значений.

7. Для скрещивания точка кроссовера в хромосоме устанавливается произвольно, и обмениваемые фрагменты строк тоже выбираются произвольно. Обычно делят хромосому пополам. Менять целесообразно только правые части, как более чувствительные (точные) – они являются разрядами единиц и десятков (в 10-й системе счисления).

При использовании двухточечного кроссовера хромосома разбивается на 3 части двумя точками, и обмен производится только средними фрагментами – разряды десятков и сотен в 10-й системе счисления.

Остальные позиции (гены) изменяются посредством мутации хромосом.

8. Мутация хромосом производится достаточно редко. Каждый бит каждой особи популяции с вероятностью мутации p_m инвертируется. Эта вероятность обычно очень мала, менее 1%. Одновременно можно мутировать все особи, хотя обычно достаточно изменять один ген в одной особи. Особь и номер её гена можно определить с помощью ГСЧ – функция СЛЧИСЛ в MS Excel.

9. После мутации ГА должен проверять, не вышла ли особь из своего диапазона изменения. Если вышла, посредством ГСЧ определяется другой ген мутирования.

10. Каждый результат итерации проверяется функцией приспособленности. Если функция увеличилась (при поиске максимума), то для следующего скрещивания берутся полученные особи хромосомы, если нет – то особи наилучшего результата. Тем самым моделируется естественный отбор – неудачные особи вымирают, удачные – прогрессируют, развиваются, приспосабливаются.

11. При отсутствии математической функции приспособленности – целевой функции управления приспособленность каждого варианта хромосомы (каждой итерации) проверяется на практике – на реальном объекте, для которого разрабатывается ГА.

12. Сходимость ГА определяется неоднократным (5-6 раз) повторением " хорошего" результата. Это означает, что дальнейшее скрещивание и мутация особей не приводит к их существенному улучшению и ГА нужно остановить.

13. Для того, чтобы выявить другие оптимумы или убедиться, что в пространстве поиска существует только один экстремум, ГА нужно запустить несколько раз. При устойчивом получении одинаковых результатов можно сделать вывод об унимодальности пространства (наличии одного оптимума).

 

Контрольные вопросы

1. Что называется генетическим алгоритмом, где он применяется?

2. Как выбирается начальная популяция, определяется длина хромосомы?

3. Как работает кроссовер, виды кроссоверов?

4. Правила выполнения скрещивания.

5. Правила выполнения мутации

6. Как определяется конец вычислений - схождение ГА?