Простой генетический алгоритм

Для применения генетического алгоритма необходимо:

1. выделить совокупность свойств объекта, характеризуемых внутренними параметрами и влияющих на его полезность, т.е. выделить множество управляемых параметров среди могут быть величины различных типов (real, integer, Boolean, enumeration). Наличие нечисловых величин (enumeration) обусловливает возможность решения задач не только параметрической, но и структурной оптимизации;

2. сформулировать количественную оценку полезности вариантов объекта - функцию полезности . Если в исходном виде задача многокритериальна, то такая формулировка означает выбор скалярного (обобщенного) критерия;

. разработать математическую модель объекта, представляющую собой алгоритм вычисления для заданного вектора ;

. представить вектор в форме хромосомы - записи следующего вида (см. рис. 1).

Рис. 1. Хромосома

В генетическом алгоритме используется такая терминология:

· ген - управляемый параметр ;

· аллель - значение гена;

· локус (позиция) - позиция, занимаемая геном в хромосоме;

· генотип - экземпляр хромосомы, генотип представляет совокупность внутренних параметров проектируемого с помощью генетического алгоритма объекта;

· генофонд - множество всех возможных генотипов;

· функция полезности (приспособленности) - целевая функция;

· фенотип - совокупность значений критериев, получаемых после декодирования хромосомы, под фенотипом часто понимают совокупность выходных параметров синтезируемого с помощью генетического алгоритма объекта.

Вычислительный процесс начинается с генерации исходного поколения множества, включающего хромосом, - размер популяции. Генерация выполняется случайным выбором аллелей каждого гена.

Далее организуется циклический процесс смены поколений:

for k=1:G

for j=1:N

Выбор родительской пары хромосом;

Кроссинговер;

Мутации;

Оценка функции полезности F потомков;

Селекция;

end

Замена текущего поколения новым;

end

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

Рассмотрим алгоритмы выполнения операторов в простом генетическом алгоритме.