1. Основы теории генетических алгоритмов

Генетические алгоритмы представляют собой алгоритмы поиска, построенные на принципах, сходных с принципами естественного отбора и генетики. Они объединяют в себе принцип выживания наиболее перспективных особей – решений и упорядоченный обмен информацией между отдельными решениями, в котором присутствует элемент случайности, аналогичный процессам мутаций в живой природе.

Можно выделить следующие основные принципы при построении генетических алгоритмов:

1. Вначале работы каким-либо образом выбираются значения целевой функции, соответствующие набору точек в пространстве состояний (это может быть реализовано в процессе работы другого метода, либо такие точки выбираются произвольно). Далее значения целевой функции, соответствующие различным точкам пространства состояний кодируются, и каждое такое решение записывается в строке двоичного кода фиксированной длины. Каждая такая строка, соответствующая целевой функции в фиксированной точке пространства состояний, называется хромосомой. На следующем этапе происходит изменение первичных хромосом, аналогичное мутациям в живых организмах. Оно может осуществляться целым рядом различных способов: изменением знака отдельных бит в хромосоме, путем обмена между хромосомами отдельными битами-генами, путем обмена целыми кусками хромосом и т.д. Основной особенностью этого процесса является то, что он никак не связан с содержанием хромосом (т.е. степенью оптимальности целевой функции). Вычисление целевой функции производится до образования хромосом и после цикла их мутирования (таких циклов может быть множество). В промежутке же мы обращаемся со всеми хромосомами как совершенно равноправными объектами.

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

3. Генетические алгоритмы в процессе работы (мутаций) не используют никакой дополнительной информации, что существенно повышает скорость их работы.

Собственно сам процесс работы генетического алгоритма выглядит следующим образом:

• выбирается первый набор значений целевой функции и далее каждой точке пространства независимых переменных ставится в соответствие хромосома (ее могут называть также особью);

• далее по определенным правилам происходит процесс мутации хромосом. После этапа мутации восстанавливаются точки пространства переменных (в результате мутации происходит некоторое смещение точек от первоначальных положений) и соответствующие смещенным точкам значения целевой функции.

• Далее происходит отбор значений целевой функции, на основании которых образуется набор хромосом второго поколения. Как правило, происходит не отбор значений, имеющих максимальное значение целевой функции, а лишь повышение вероятности попасть в следующий тур. Затем происходит кодирование координат отобранных точек и процесс повторяется большое количество раз: либо до получения приемлемого результата, либо до выхода на насыщение с неудовлетворительными результатами. В этом случае весь процесс расчета повторяется с новыми значениями параметров эволюции: например, количеством хромосом, вероятности попадания лучших значений в следующий тур, параметров мутации и т.п.