Генетические алгоритмы в задаче оптимизации действительных параметров

Идея генетических алгоритмов заимствована у живой природы и состоит в организации эволюционного процесса, конечной целью которого является получение оптимального решения в сложной комбинаторной задаче. Разработчик генетических алгоритмов выступает в данном случае как "создатель", который должен правильно установить законы эволюции, чтобы достичь желаемой цели как можно быстрее.

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

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

Генетический алгоритм - это простая модель эволюции в природе, реализованная в виде компьютерной программы. В нем используются как аналог механизма генетического наследования, так и аналог естественного отбора. При этом сохраняется биологическая терминология в упрощенном виде. Представим себе искусственный мир, населенный множеством существ (особей), причем каждое существо — это некоторое решение нашей задачи. Будем считать особь тем более приспособленной, чем лучше соответствующее решение (чем большее значение целевой функции оно дает). Тогда задача максимизации целевой функции сводится к поиску наиболее приспособленного существа. Конечно, мы не можем поселить в наш виртуальный мир все существа сразу, так как их очень много. Вместо этого мы будем рассматривать много поколений, сменяющих друг друга. Теперь, если мы сумеем ввести в действие естественный отбор и генетическое наследование, то полученный мир будет подчиняться законам эволюции. Заметим, что, в соответствии с нашим определением приспособленности, целью этой искусственной эволюции будет как раз создание наилучших решений. Очевидно, эволюция — бесконечный процесс, в ходе которого приспособленность особей постепенно повышается. Принудительно остановив этот процесс через достаточно долгое время после его начала и выбрав наиболее приспособленную особь в текущем поколении, мы получим не абсолютно точный, но близкий к оптимальному ответ. Такова, вкратце, идея генетического алгоритма.

эволюция генетический хромосома

1. Эволюция в природе

1.1 Естественный отбор

Можно сказать, что эволюция - это процесс оптимизации всех живых организмов. Ключевую роль в эволюционной теории играет естественный отбор. Его суть состоит в том, что наиболее приспособленные особи лучше выживают и приносят больше потомства, чем менее приспособленные. Заметим, что сам по себе естественный отбор еще не обеспечивает развития биологического вида. Действительно, если предположить, что все потомки рождаются примерно одинаковыми, то различные поколения будут отличаться только по численности, но не по приспособленности. Поэтому очень важно изучить, каким образом происходит наследование, т. е. как свойства потомка зависят от свойств родителей. Основной закон наследования интуитивно понятен каждому — он состоит в том, что потомки похожи на родителей. В частности, потомки более приспособленных родителей будут, скорее всего, одними из наиболее приспособленных в своем поколении. Чтобы понять, на чем основана эта похожесть, нам потребуется немного углубиться в строение животной клетки — в мир генов и хромосом. Почти в каждой клетке любого животного имеется набор хромосом, несущих информацию об этом животном. Основная часть хромосомы — нить ДНК (молекула дезоксирибонуклеиновой кислоты), которая состоит из четырех видов специальных соединений — нуклеотидов, идущих в определенной последовательности. Нуклеотиды обозначаются буквами A, T, C и G, и именно порядок их следования кодирует все генетические свойства данного организма. Говоря более точно, ДНК определяет, какие химические реакции будут происходить в данной клетке, как она будет развиваться и какие функции выполнять. Ген — это отрезок цепи ДНК, отвечающий за определенное свойство особи, например за цвет глаз, тип волос, цвет кожи и т. д. Вся совокупность генетических признаков человека кодируется посредством примерно 60 тыс. генов, суммарная длина которых составляет более 90 млн. нуклеотидов. Различают два вида клеток: половые (такие, как сперматозоид и яйцеклетка) и соматические. В каждой соматической клетке человека содержится 46 хромосом. Эти 46 хромосом — на самом деле 23 пары, причем в каждой паре одна из хромосом получена от отца, а вторая — от матери. Парные хромосомы отвечают за одни и те же признаки — например, отцовская хромосома может содержать ген черного цвета глаз, а парная ей материнская — ген голубоглазости. Существуют определенные законы, управляющие участием тех или иных генов в развитии особи. В частности, в нашем примере потомок будет черноглазым, так как ген голубых глаз является «слабым» (рецессивным) и подавляется геном любого другого цвета.

В половых клетках хромосом только 23, и они непарные. При оплодотворении происходит слияние мужской и женской половых клеток и образуется клетка зародыша, содержащая как раз 46 хромосом. Какие свойства потомок получит от отца, а какие — от матери? Это зависит от того, какие именно половые клетки участвовали в оплодотворении. Дело в том, что процесс выработки половых клеток (так называемый мейоз) в организме подвержен случайностям, благодаря которым потомки все же во многом отличаются от своих родителей. При мейозе, в частности, происходит следующее: парные хромосомы соматической клетки сближаются вплотную, затем их нити ДНК разрываются в нескольких случайных местах и хромосомы обмениваются своими частями.

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

1.2 Задачи оптимизации

Как уже было отмечено выше, эволюция — это процесс постоянной оптимизации биологических видов. Теперь мы в состоянии понять, как происходит этот процесс. Естественный отбор гарантирует, что наиболее приспособленные особи дадут достаточно большое потомство, а благодаря генетическому наследованию мы можем быть уверены, что часть этого потомства не только сохранит высокую приспособленность родителей, но будет обладать и некоторыми новыми свойствами. Если эти новые свойства окажутся полезными, то с большой вероятностью они перейдут и в следующее поколение. Таким образом, происходит накопление полезных качеств и постепенное повышение приспособляемости биологического вида в целом. Зная, как решается задача оптимизации видов в природе, мы теперь применим похожий метод для решения различных реальных задач. Задачи оптимизации — наиболее распространенный и важный для практики класс задач. Их приходится решать каждому из нас либо в быту, распределяя свое время между различными делами, либо на работе, добиваясь максимальной скорости работы программы или максимальной доходности компании — в зависимости от должности. Среди этих задач есть решаемые простым путем, но есть и такие, точное решение которых найти практически невозможно. Введем обозначения и приведем несколько классических примеров. Как правило, в задаче оптимизации мы можем управлять несколькими параметрами (обозначим их значения через x1, x2, ..., xn, а нашей целью является максимизация (или минимизация) некоторой функции, f(x1, x2, ..., xn), зависящей от этих параметров. Функция f называется целевой функцией. Например, если требуется максимизировать целевую функцию «доход компании», то управляемыми параметрами будут число сотрудников компании, объем производства, затраты на рекламу, цены на конечные продукты и т. д. Важно отметить, что эти параметры связаны между собой — в частности, при уменьшении числа сотрудников скорее всего упадет и объем производства. Конечно, математики издавна занимались подобными задачами и разработали несколько методов их решения. В случае если целевая функция достаточно гладкая и имеет только один локальный максимум (унимодальная), то оптимальное решение можно получить методом градиентного спуска. Идея этого метода состоит в том, что оптимальное решение получается итерациями. Берется случайная начальная точка, а затем в цикле происходит сдвиг этой точки на малый шаг, причем шаг делается в том направлении, в котором целевая функция растет быстрее всего. Недостатком градиентного алгоритма являются слишком высокие требования к функции — на практике унимодальность встречается крайне редко, а для неправильной функции градиентный метод часто приводит к неоптимальному ответу. Аналогичные проблемы возникают и с применением других математических методов. Во многих важных задачах параметры могут принимать лишь определенные значения, причем во всех остальных точках целевая функция не определена. Конечно, в этом случае не может быть и речи о ее гладкости, и требуются принципиально другие подходы. Таким образом, возникает необходимость в каком-либо новом методе оптимизации, пригодном для практики. Здесь и появляется необходимость в каких-то новых методах решения, например таких, как генетический алгоритм.

2. Генетический алгоритм

2.1 История развития ГА

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

Другой отправной точкой развития исследований по генетическим алгоритмам была публикация в 1975 году книги Холланда "Adaptation in Natural and Artificial Systems". Эта книга заложила теоретический фундамент для работы де Джонга и всех последующих работ, математически обосновав идею близких подмножеств внутри генотипа, процессов гибели и селективного воспроизведения. Цели этой книги были достаточно широкими. Хотя доказательства основных утверждений были представлены для генов фиксированной длины и соответствующих простых операторов, это не ограничивало развитие представленного подхода на случаи более богатые по своим возможностям. Например, Холланд обсуждал возможность применения операторов внутрихромосомной дупликации, удаления и сегрегации участков хромосомы.

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

Только небольшая часть исследователей предприняла усилия по разработке альтернативных схем. Среди них выделяются детектор паттернов Кавичио, работа Франца по инверсии, игрок в покер Смита.

Исследование Кавичио, нацеленное на разработку детектора распознавания образов было одним из первых, использующих гены переменной длины. Расположенные на плоскости двоичные пиксели, способные различать свет и темноту, нумеровались и объединялись в подмножества, образующие разные детекторы, которые затем использовались некоторым априорно заданным алгоритмом для распознавания образов. При этом не возникало использование одного и того же пикселя дважды или не использования пикселя.

Смит использовал правила, оперирующие строками переменной длины, создавая модель машинного игрока в покер. Его LS-1 система использовала модифицированный кроссинговер, который располагал точки кроссинговера как на границах строк, кодирующих правила, так и внутри них. Он также включил в алгоритм оператор инверсии, надеясь, что это поможет более эффективно распределять правила внутри строки.

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

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

2.2 Общий вид генетического алгоритма

Вначале ГА-функция генерирует определенное количество возможных решений. Задается функция оптимальности , определяющая эффективность каждого найденного решения, для отслеживания выхода решения из допустимой области в функцию можно включить штрафной компонент. Каждое решение кодируется как вектор x, называемый хромосомой. Его элементы – гены, изменяющиеся в определённых позициях, называемых аллелями. Геном – совокупность всех хромосом. Генотип – значение генома.

Рис. 2. Структура хромосомы

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

Таблица 1. Код Грея