Генетические алгоритмы в разработке программно-информационных систем

ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ В РАЗРАБОТКЕ ПРОГРАММНО-ИНФОРМАЦИОННІХ СИСТЕМ Скобцов Ю. А. Санкт-Петербург 2017 1 «ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ В РАЗРАБОТКЕ ПРОГРАММНО-ИНФОРМАЦИОННЫХ СИСТЕМ» Краткая аннотация. Рассмотрены основы нового направления в теории искусственного интеллекта, включающего генетические алгоритмы. Изложены классические генетические алгоритмы и их современные модификации. Цель курса: Курс предназначен для студентов, аспирантов и преподавателей специальностей, обучающихся по направлениям "Программная инженерия", а также широкому кругу специалистов, занимающихся интеллектуальными системами обработки информации. Цель – применение генетических алгоритмов в проектировании программноинформационных систем» Предварительные знания: Высшая математика, дискретная математика, методы оптимизации, основы искусственного интеллекта. 2 11 Предисловие Среди множества проблем, которые возникают перед исследователями как в области теории, так и в многочисленных практических приложениях значительную долю составляют так называемые оптимизационные проблемы. Понятие оптимальности, по-видимому, знакомо почти каждому и вошло в практику большинства предметных областей. С оптимизационной проблемой мы сталкиваемся каждый раз, когда возникает необходимость выбора из некоторого множества возможных решений наилучшего по определенным критериями и, как правило, удовлетворяющего заданным условиям и ограничениям. Само понятие оптимальности получает совершенно строгое толкование в математических теориях, однако в других областях оно может интерпретироваться скорее содержательно. Тем не менее различие между строгим и содержательным понятиями оптимальности, как правило, очень незначительно. Существуют классы оптимизационных задач, решение которых удается находить с помощью достаточно эффективных методов, вполне приемлемых по трудоемкости. Вместе с тем имеются и такие классы оптимизационных задач (так называемые NP- полные задачи), решение которых невозможно найти без полного перебора вариантов. В частности, к числу последних относятся многие разновидности задач многокритериальной оптимизации. Известно, что при большой размерности этих задач реализация перебора вариантов практически невозможна из-за чрезвычайно больших временных затрат. В этой ситуации альтернативным походом к решению упомянутых задач является применение методов, базирующихся на методологии эволюционных вычислений. Предлагаемое пособие содержит изложение основ эволюционных вычислений и их приложений к решению различных проблем, включая проблемы экономики, прогнозирования финансовых рынков, инвестиций, бизнеса, комбинаторной оптимизации, сложных задач в различных технических разработках и т.п. Эффективность различных методов в рамках эволюционного подхода подтверждается многочисленными данными, касающимися достигаемым реальным эффектом. При этом хотя объем вычислений может оказаться большим, но скорость, с которой он растет при увеличении размерности задачи, обычно меньше, чем у остальных известных методов. Отметим, что после того как компьютерные системы стали достаточно быстродействующими и недорогими, эволюционные методы превратились в важный инструмент поиска близких к оптимальным решений задач, которые до этого считались неразрешимыми. Основной целью учебного пособия является систематическое изложение перспективного направления в области теории и практики искусственного интеллекта. Пособие рассчитано на студентов и аспирантов вузов, обучающихся по направлениям, связанным с прикладной информатикой и 11 12 математикой, компьютерными и программными системами, с интеллектуальными системами обработки информации. Освоение представленного в пособии материала предполагает знакомство читателя с математикой и информатикой в объеме первых двух курсов технического вуза, основами дискретной математики и методов оптимизации. 12 13 Введение В настоящее время оформилось и успешно развивается новое направление в теории и практике искусственного интеллекта – эволюционные вычисления (ЭВ). Этот термин обычно используется для общего описания алгоритмов поиска, оптимизации или обучения, основанных на некоторых формализованных принципах естественного эволюционного отбора. Особенности идей эволюции и самоорганизации заключаются в том, что они являются плодотворными и полезность их применения не только для биологических систем перманентно подтверждается. Эти идеи в настоящее время с успехом используются при разработке многих технических и, в особенности, программных систем. Высокая согласованность и эффективность работы элементов биологических систем приводила целый ряд исследователей к естественной мысли о возможности использования принципов биологической эволюции для оптимизации важных для приложений систем, природа которых отлична от биологической. Так, в 1966 году Фогель Л., Оуенс С. и Уолш М. в подобную идею использовали для построения схемы эволюции логических автоматов, решающих задачи прогноза. В 1975 году была опубликована основополагающая работа Дж. Холланда , в которой был предложен генетический алгоритм, развивающий ту же идею. Д.Гольдберг, ученик Дж. Холланда, в работе , выполненной в Мичиганском университете, успешно развил и расширил области его применения. В 60-х годах прошлого века в Германии Рохенберг И., Швефель Г.-П., и др. начали разработку так назывемой эволюционной стратегии. Перечисленные работы послужили толчком и основой развития прикладного направления, которое можно назвать эволюционными алгоритмами. К их числу, помимо упомянутых генетических алгоритмов и эволюционных стратегий, относятся также эволюционное программирование, ориентированное на оптимизацию функций без использования рекомбинаций, и генетическое программирование, использующее эволюционные идеи для оптимизации компьютерных программ. Основополагающая работа по эволюционному программированию принадлежит Дж. Коза из Массачусетского технологического института. Отметим, что аналогичные исследованиям успешно проводились отечественными учеными еще в Советском Союзе. Так, значительный вклад в развитие указанных направлений внесли Ивахненко А.Г. , Цыпкин Я.З. , Расстригин Л.А. и др. В настоящее время исследования по ЭВ активно ведутся Букатовой , Курейчиком В.М., их сотрудниками и учениками, а также многими другими исследователями. 13 14 ЧАСТЬ 1. ОСНОВЫ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ 1. Введение в генетические алгоритмы В этом разделе описывается концепция простого генетического алгоритма (ГА), ориентированного на решение различных оптимизационных задач. Вводятся и содержательно описываются понятия, используемые в теории и приложениях ГА. Приводится фундаментальная теорема ГА и излагается теория схем, составляющие теоретическую базу ГА. Обсуждаются концептуальные вопросы, касающиеся преимуществ и недостатков ГА. 1.1. Простой генетический алгоритм Основы теории генетических алгоритмов сформулированы Дж. Г.Холландом в основополагающей работе [1] и в дальнейшем были развиты рядом других исследователей. Наиболее известной и часто цитируемой в настоящее время является монография Д.Голдберга [2], где систематически изложены основные результаты и области практического применения ГА. ГА используют принципы и терминологию, заимствованные у биологической науки – генетики. В ГА каждая особь представляет потенциальное решение некоторой проблемы. В классическом ГА особь кодируется строкой двоичных символов – хромосомой, каждый бит которой называется геном. Множество особей – потенциальных решений составляет популяцию. Поиск оптимального или субоптимального решения проблемы выполняется в процессе эволюции популяции, т.е. последовательного преобразования одного конечного множества решений в другое с помощью генетических операторов репродукции, кроссинговера и мутации. ЭВ используют механизмы естественной эволюции, основанные на следующих принципах: 1) . Первый принцип основан на концепции выживания сильнейших и естественного отбора по Дарвину, который был сформулирован им в 1859 году в книге «Происхождение видов путем естественного отбора». Согласно Дарвину особи, которые лучше способны решать задачи в своей среде, чаще выживают и чаще размножаются (репродуцируют). В генетических алгоритмах каждая особь представляет собой решение некоторой проблемы. По аналогии с этим принципом особи с лучшими значениями целевой (фитнесс) функции имеют большие шансы выжить и репродуцировать. Формализацию этого принципа, как мы увидим далее, реализует оператор репродукции. 2) Второй принцип обусловлен тем фактом, что хромосома потомка состоит из частей, полученных из хромосом родителей. Этот принцип был открыт в 1865 году Г.Менделем. Его формализация дает основу для оператора скрещивания (кроссинговера). 14 15 3) Третий принцип основан на концепции мутации, открытой в 1900 году де Вре. Первоначально этот термин использовался для описания существенных (резких) изменений свойств потомков и приобретение ими свойств, отсутствующих у родителей. По аналогии с этим принципом генетические алгоритмы используют подобный механизм для резкого изменения свойств потомков и, тем самым, повышают разнообразие (изменчивость) особей в популяции (множестве решений). Эти три принципа составляют ядро ЭВ. Используя их, популяция (множество решений данной проблемы) эволюционирует от поколения к поколению. Эволюцию искусственной популяции – поиск множества решений некоторой проблемы, формально можно описать в виде алгоритма, который представлен на рис.1.1. ГА получает множество параметров оптимизационной проблемы и кодирует их последовательностями конечной длины в некотором конечном алфавите (в простейшем случае в двоичном алфавите «0» и «1») . Предварительно простой ГА случайным образом генерирует начальную популяцию хромосом (стрингов). Затем алгоритм генерирует следующее поколение (популяцию) с помощью трех следующих основных генетических операторов: 1) оператора репродукции (ОР); 2) оператора скрещивания (кроссинговера, ОК); 3) оператора мутации (ОМ). ГА работает до тех пор, пока в процессе эволюции либо будет создано заданное количество поколений (итераций), либо на некоторой генерации будет достигнуто заданное качество, либо при попадании в некоторый локальный оптимум (вследствие преждевременной сходимости). В каждом поколении множество особей формируется с использованием старых (созданных в более ранних поколениях) особей и добавлением новых (с хорошими свойствами). Генетические алгоритмы – это не просто случайный поиск, они эффективно используют информацию, накопленную в процессе эволюции. В процессе поиска решения необходимо соблюдать баланс между "эксплуатацией" полученных на текущий момент лучших решений и расширением пространства поиска. Различные методы поиска решают эту проблему по-разному. Например, градиентные методы практически основаны только на использовании лучших текущих решений, что повышает скорость сходимости с одной стороны, но порождает проблему локальных экстремумов с другой. В полярном подходе случайные методы поиска используют все пространство поиска, но имеют низкую скорость сходимости. В ГА предпринята попытка объединить преимущества этих двух противоположных подходов. При этом операторы репродукции и кроссинговера делают поиск направленным. Широту поиска обеспечивает то, 15 16 что процесс ведется на множестве решений – популяции и используется оператор мутации. 1 Создание исходной популяции 2 Оценка фитнесс-функции особей в популяции 3 Выбор родителей для процесса размножения (работает оператор селекции - репродукции) 4 Создание потомков выбранных пар родителей (работает оператор скрещивания - кроссинговера) 5 Мутация новых особей (работает оператор мутации) 6 Расширение популяции за счет добавления новых только что порожденных особей 7 Сокращение расширенной популяции размера (работает оператор редукции) до исходного 8 Критерий останова работы: алгоритм выполнен? нет да 9 Поиск лучшей особи в конечной популяции. Результат работы алгоритма. Рис.1.1. Простой генетический алгоритм В отличие от других методов оптимизации ГА оптимизируют различные области пространства решений одновременно и более приспособлены к нахождению новых областей с лучшими значениями целевой функции за счет объединения квазиоптимальных решений из разных популяций. Упомянутые генетические операторы являются математической формализацией приведенных выше трех основополагающих принципов Ч.Дарвина, Г.Менделя и де Вре естественной эволюции. Каждый из 16 17 функциональных блоков ГА на рис. 1.1 может быть реализован различными способами. Но сначала на простом примере мы рассмотрим основные моменты классического ГА. 1.2. Генетические операторы Рассматриваемый ниже пример заимствован из популярной монографии Голдберга [2] и состоит в поиске целочисленного значения (для простоты) х на отрезке от [0,31], при котором функции y  x 2 принимает максимальное значение. y 1200 f ( x)  x 2 1000 800 600 400 200 5 10 15 20 25 30 x Рис.1.2. Пример функции Начальный этап работы ГА для данного примера приведен в верхней таблице (репродукция) рис.1.3. Здесь особи начальной популяции (двоичные коды значений переменных х - столбец 2) сгенерированы случайным образом. Двоичный код значения х называется хромосомой (она представляет генотип). Популяция образует множество потенциальных решений данной проблемы. В третьем столбце представлены их десятичные значения (фенотип). Далее на этом примере проиллюстрируем работу трех основных генетических операторов. 1.2.1. Репродукция Репродукция – это процесс, в котором хромосомы копируются в промежуточную популяцию для дальнейшего "размножения" согласно их значениям целевой (фитнесс-) функции. При этом хромосомы с лучшими значениями целевой функции имеют большую вероятность попадания одного или более потомков в следующее поколение. Очевидно, оператор репродукции (ОР) является искусственной версией естественной селекции – выживания сильнейших по Ч. Дарвину. Этот оператор представляется в алгоритмической форме различными способами (подробнее различные варианты ОР будут рассмотрены далее). Самый простой (и популярный) метод реализации ОР – построение колеса рулетки, в которой каждая хромосома имеет сектор, пропорциональный по площади значению ее целевой функции. Для нашего примера "колесо рулетки" имеет вид, представленный на рис.1.4. 17 18 Для селекции хромосом используется случайный поиск на основе колеса рулетки. При этом колесо рулетки вращается и после останова ее указатель определяет хромосому для селекции в промежуточную популяцию (родительский пул). Репродукция № Начальная хромо популяци -сомы я особей 1 2 3 4 01101 11000 01000 10011 Десятичн ое значение x 13 24 8 19 Значени е f(x) f(x ) i  f(x j ) 169 576 64 361 0,14 0,49 0,06 0,31 Среднее Максимальн значени ое значение е f(x) f max (x) 293 576 Кроссинговер Пары Популяци Популяция № хромосом я после после Значени хромо для репродукц кроссинго е f(x) -сомы кроссинго ии вера вера 1 01101 1-2 01100 144 2 11000 1-2 11001 625 3 11000 3-4 11011 729 4 10011 3-4 10000 256 Среднее Максимальн значени ое значение е f(x) f max (x) 439 729 Мутация Популяция № после хромо кроссинго -сомы вера 1 01100 2 11001 3 11011 4 10000 Новая популяция после мутации 01100 11001 11111 10000 Десятичн ое значение x 12 25 31 16 Значени е f(x) 144 625 961 256 Среднее Максимальн значени ое значение е f(x) f max (x) 496.5 961 Рис.1.3. Эволюция популяции Очевидно, что хромосома, которой соответствует больший сектор рулетки, имеет большую вероятность попасть в следующее поколение. В результате выполнения оператора репродукции формируется промежуточная популяция, хромосомы которой будут использованы для построения поколения с помощью операторов скрещивания. 18 19 В нашем примере выбираем хромосомы для промежуточной популяции, вращая колесо рулетки 4 раза, что соответствует мощности f(xi ) начальной популяции. Величину обозначим как P(xi ) , тогда  f(x j ) ожидаемое количество копий i-ой хромосомы определяется значением M= P(xi ) *N, где N-мощность популяции. Число копий хромосомы, ~ f(x ) переходящих в следующее поколение, иногда определяется и так: M  i , f(x) где f(x) - среднее значение хромосомы в популяции. 14% 31% 1 4 3 2 6% 49% Рис.1.4. Колесо рулетки Расчетные числа копий хромосом по приведенной формуле следующие: хромосома 1 - 0,56; хромосома 2 - 1,97; хромосома 3 – 0,22; хромосома 4 – 1,23. В результате, в промежуточную популяцию 1-я хромосома попадает в одном экземпляре, 2-я – в двух, 3-я – совсем не попадает, 4-я – в одном экземпляре. Полученная промежуточная популяция является исходной для дальнейшего выполнения операторов кроссинговера и мутации. 1.2.2 Оператор кроссинговера (скрещивания) Одноточечный или простой оператор кросинговера (ОК) с заданной вероятностью Pc выполняется в три этапа: 1-й этап. Две хромосомы (родители) Точка кроссинговера A= a1a 2 ...a k a k 1...aL B= b1b2 ...bk bk 1...bL 19 20 выбираются случайно (или одним из методов, рассмотренных далее) из промежуточной популяции, сформированной при помощи оператора репродукции (ОР). 2-й этап. Случайно выбирается точка скрещивания - число k из диапазона [1,n-1], где n – длина хромосомы (число бит в двоичном коде). 3-й этап. Две новых хромосомы A', B' (потомки) формируются из A и B путем обмена подстрок после точки скрещивания: A= a1a 2 ...a k bk 1...bL B= b1b2 ...bk a k 1...aL Например, рассмотрим выполнение кроссинговера для хромосом 1 и 2 из промежуточной популяции: A=0 1 1 0 1 B=1 1 0 0 0 1  k  4, k=4 A=0 1 1 0 0 B=1 1 0 0 1 Следует отметить, что ОК выполняется с заданной вероятностью Pc (отобранные два родителя не обязательно производят потомков). Обычно величина вероятности полагается равной Pc  0.5 . Таким образом, операторы репродукции и скрещивания очень просты – они выполняют копирование особей и частичный обмен частей хромосом. Продолжение нашего примера представлено на рис.1.3 во второй таблице (кроссинговер). Сравнение с предыдущей таблицей показывает, что в промежуточной популяции после скрещивания улучшились все показатели популяции (среднее и максимальное значения целевой функции - ЦФ). 1.2.3 Мутация Далее согласно схеме классического ГА с заданной вероятностью Pм выполняется оператор мутации. Иногда этот оператор играет вторичную роль. Обычно вероятность мутации мала - Pm  0,001. Оператор мутации (ОМ) выполняется в два этапа: 1-й этап. В хромосоме A= a1a 2 ...a L случайным образом выбирается k-ая позиция (бит) (1 k  n). 2-й этап. Производится инверсия значения гена в k-й позиции: a 'k  a k . Например, для хромосомы 11011 выбирается k=3 и после инверсии значения третьего бита получается новая хромосома – 11111. Продолжение нашего примера представлено в третьей таблице (мутация) рис.1.3.Таким образом, в результате применения генетических операторов найдено оптимальное решение x=31. 20 21 В данном случае, поскольку пример искусственно подобран, мы нашли оптимальное решение за одну итерацию. В общем случае ГА работает до тех пор, пока не будет выполнен критерий окончания процесса поиска и в последнем полученном поколении определяется лучшая особь, которая и принимается в качестве решения задачи. 1.3. Представление вещественных решений в двоичной форме В предыдущем примере мы рассматривали только целочисленные решения. Обобщим ГА на случай вещественных чисел на примере функции f(x)=(1,85 -x)*cos(3,5x – 0,5), представленной на рис.1.5 [4]. Рассматривается та же задача: необходимо найти вещественное x  [10,10] , которое максимизирует f(х), т.е. такое x0 , для которого f x0   f x  для всех х   10,10 . Рис.1.5. Пример функции с популяцией особей в начале эволюции Для решения этой задачи с помощью ГА будем использовать представления вещественного решения (хромосомы) x в виде двоичного вектора [5], который применяется в классическом простом ГА. Его длина зависит от требуемой точности решения, которую в данном случае положим, например, равной 3 знакам после запятой. Поскольку отрезок области решения имеет длину 20, для достижения заданной точности отрезок [a,c]= [-10,+10] должен быть разбит на равные части (маленькие отрезки), число которых должно быть не менее 20*1000. В качестве двоичного представления используем двоичный код номера 21 22 (маленького) отрезка. Этот код позволяет определить соответствующее ему вещественное число, если известны границы области решения. Отсюда следует, что двоичный вектор для кодирования вещественного решения должен иметь 15 бит, поскольку 16384= 214 <20000  215  32768 Отсюда следует, что для обеспечения необходимой точности требуется разбить отрезок [-10,+10] на 32768 частей. Отображение из двоичного представления ( b14b13...b0 ) ( bi {0,1} ) в вещественное число из отрезка [a,c]=[-10,+10] выполняется в два шага. 1) Перевод двоичного числа в десятичное:  14   b14 b13 ...b0 2    bi 2 i   X   i 0 10 2) Вычисление соответствующего вещественного числа х: x  a  x  (c  a ) 20  10  x  15 15 2 1 2 1 , где (– 10) левая граница области решения. Естественно хромосомы (000000000000000) и (111111111111111) представляют границы отрезка –10 и +10 соответственно. Очевидно, при данном двоичном представлении вещественных чисел можно использовать классический простой ГА. На рис.1.6–1.8 представлено расположение особей (потенциальных решений) на различных этапах ГА в процессе поиска решения[4]. На рисунке 1.5 показана начальная популяция потенциальных решений, которая равномерно покрывает область поиска решения. Далее явно видно, как постепенно с увеличением номера поколения особи "конденсируются" в окрестностях экстремумов и, в конечном счете, находится лучшее решение. 22 23 Рис.1.6. Начальная «конденсация» особей популяции в окрестностях экстремумов Для сокращения длины хромосом иногда применяют логарифмическое кодирование, при котором первый бит (a) кодовой последовательности используется для знака показательной функции, второй бит (b) – для знака степени этой функции, и остальные биты (str) представляют значение самой степени [6]. Таким образом, двоичный код представляет вещественное число (1)b e ( 1) [ str ]10 . Здесь представленное двоичным кодом str. a 23 [str ]10 означает десятичное число, 24 Рис.1.7. «Конденсация» особей в окрестностях экстремумов Рис.1.8. Положение особей популяции в конце эволюции Например, двоичный код число (1) e ( 1)1 [110]10 <10101> представляет вещественное  e  0,002478752 . Следует отметить, что при таком 6 24 25 кодировании пять битов позволяет кодировать вещественные числа из интервала [-e7, e7], что значительно больше, чем это позволяет, например, метод кодирования, представленный ранее. 1.4. Использование кода Грея в ГА Рассмотренное двоичное представление вещественного числа имеет существенный недостаток: расстояние между вещественными числами (на числовой оси) часто не соответствует расстоянию (по Хеммингу) между их двоичными представлениями. Поэтому желательно получить двоичное представление, где близкие расстояния между хромосомами (двоичными представлениями) соответствовали близким расстояниям в проблемной области (в данном случае расстоянию на числовой оси) [2,4,5]. Это можно сделать, например, с помощью кода Грея. В таблице 1.4 приведен для примера код Грея для 4-х битовых слов. Двоичный код 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Таблица 1.4 Код Грея 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 Заметим, что в коде Грея соседние двоичные слова отличаются на один бит (расстояние по Хеммингу равно1). Рассмотрим алгоритмы преобразования двоичного числа b  b1,...,bm  в код Грея g  g1,...,gm  и наоборот. Procedure Binary-to-Gray() { g1=b1 25 26 for k=2 to m do gk=bk-1 xor bk } Procedure Gray-to-Binary { value=g1 b1=value for k=2 to m do begin if gk=1 then value=NOTvalue bk=value } end Рис.1.9 Преобразование в код Грея Здесь параметр m определяет разрядность двоичного числа. Существует и другая, матричная, процедура преобразования в код Грея. Например, для m=4 матрицы 1000  1100   A 0110   0011 и A1 1000 1100   1110   1111 позволяют выполнять следующие преобразования: g  A  b и b  A1g , где умножение матриц выполняются в арифметике по mod 2. Отметим, что применение кода Грея прежде всего оправдано при использовании операторов мутации. 1.5. Фитнесс-функция Как видно из основной блок-схемы ГА на рис.1.1, каждая особь популяции (потенциальное решение проблемы) оценивается путем вычисления значения фитнесс-функции. Следует отметить, что в общем случае целевая функция (ЦФ) и фитнесс-функция могут различаться. Целевая функция предназначена для оценки характеристик особи относительно конечной цели (например, экстремумов). Фитнесс-функция предназначена, прежде всего, для отбора особей для дальнейшей репродукции и здесь важны характеристики качества одной особи относительно других особей. После декодирования хромосомы, где выполняется преобразование «генотип  фенотип» (например, двоичный код преобразуется в 26 27 вещественное число), полученное значения далее используется в качестве аргумента для фитнесс-функции. Далее для каждой особи популяции вычисляются значения фитнесс-функции, которые ранжируют эти особи относительно друг друга в смысле перспективности получения из них хорошего решения. Определение соответствующей фитнесс-функции является решающим для корректной работы ГА. В частности, вид фитнесс-функции может зависеть от накладываемых ограничений при решении оптимизационных задач. Отметим, что операторы кроссинговера и мутации не учитывают, попадают ли вновь построенные особи-потомки в область допустимых решений, которая обусловлена накладываемыми ограничениями. В ГА используются четыре основных метода для учета накладываемых ограничений при решении оптимизационных задач. Вероятно, простейшим способом является метод отклонения (отбрасывания), где недопустимые хромосомы (не удовлетворяющие ограничениям) исключаются из дальнейшей эволюции. Второй метод основан на использовании процедуры восстановления, которая преобразует полученное недопустимое решение в допустимое. Другой альтернативой является применение проблемноориентированных генетических операторов, которые порождают только допустимые решения. Рассмотренные методы не строят недопустимых решений. Но это не всегда дает хорошие результаты. Например, в том случае, когда оптимальные решения лежат на границе допустимой области, указанные методы могут давать неоптимальные решения. Одним из возможных вариантов преодоления этой проблемы является выполнение процедуры восстановления только для некоторого подмножества решений (например, 10% особей). Для решения оптимизационных задач со сложными ограничениями иногда позволяют вести поиск решения и в недопустимых областях. Реализуется это подход часто с помощью метода штрафных функций, что позволяет расширить пространство поиска решений. Следует отметить, что часто недопустимая точка, близкая к оптимальному решению, содержит больше полезной информации, чем допустимая точка, далекая от оптимума. С другой стороны, построение штрафных функций является достаточно сложной проблемой, которая сильно зависит от решаемой задачи. Обычно нет априорной информации о расстоянии до оптимальных точек, есть только расстояние до границы области допустимых решений. Поэтому, как правило, штрафные функции используют расстояние до границ допустимой области. Штрафы, основанные на нарушении отдельных ограничений, работают обычно не очень хорошо. Разработаны два основных способа построения штрафных функций со штрафным термом: аддитивная и мультипликативная формы. В первой форме функция представляется в виде g ( x)  f ( x)  p( x) , где при максимизации для допустимых точек p( x)  0 и в противном случае 27 28 p( x)  0 . Максимум значения p(x) по абсолютной величине не может быть больше, чем минимальное значение f (x) по абсолютной величине для любой генерации, чтобы избежать отрицательных фитнесс-значений. Мультипликативная форма представляет функцию в виде g ( x)  f ( x)  p( x) , где при максимизации p( x)  1 для допустимых точек и 0  p( x)  1 в противном случае. При этом штрафной терм должен изменяться не только в зависимости от степени нарушения ограничения, но и от номера поколения ГА. Наряду с нарушением ограничения, штрафной терм обычно содержит штрафные коэффициенты (по одному для каждого ограничения). На практике большую роль играют значения этих коэффициентов. Маленькие значения коэффициентов могут привести к недопустимым значениям решения, в то время как большие значения полностью отвергают недопустимые подпространства. В среднем абсолютные значения целевой и штрафной функции должны быть соизмеримы. При таком подходе параметры штрафной функции можно включить в параметры ГА, что позволяет разработать адаптивный метод, где значения коэффициентов регулируются в процессе поиска решения. В целом на выбор (построение) фитнесс-функции оказывают влияние следующие факторы: - тип задачи – максимизация или минимизация; - содержание шумов окружающей среды в фитнесс-функции; - возможность динамического изменения фитнесс-функции в процессе решения задачи; - объем допустимых вычислительных ресурсов – допускается ли использовать более точные методы и значительные ресурсы, или возможны только приближенные аппроксимации, не требующие больших ресурсов; - насколько различные значения для особей должна давать фитнесс-функция для облегчения отбора родительских особей; - должна ли она содержать ограничения решаемой задачи; - может ли она совмещать различные подцели (например, для многокритериальных задач). В ГА фитнесс-функция используется в виде черного ящика: для данной хромосомы она вычисляет значение, определяющее качество данной особи. Внутри она может быть реализована по-разному: в виде математической функции, программы моделирования (в том числе имитационного), нейронной сети, или даже экспертной оценки. Для некоторых задач оценку значений фитнесс-функции можно выполнять с помощью объектно-ориентированной имитационной модели. Взаимодействие такой модели с ГА показано на рис.1.9. Объектная модель Вычисление критериев эффективности Фитнесс-функция 28 Генетический алгоритм Начальная популяция 29 Рис. 1.9. Схема взаимодействия объектной модели с ГА. 1.6. Параметры генетических алгоритмов Эффективность ГА зависит от ряда параметров, к которым относятся: мощность популяции, структура представления решения, вид генетических операторов кроссинговера и мутации, вероятности кроссинговера и мутации Pc и Pm и т.п.. Мощность популяции N является важнейшим параметром ГА, который критичен во многих приложениях. Чем больше N, тем больше разнообразие потенциальных решений (при хорошей схеме инициализации, обеспечивающей однородное распределение частиц). Большое число особей позволяет покрыть большую часть пространства поиска за одну итерацию. С другой стороны, большое число особей повышает вычислительную сложность итерации и при этом ГА может выродиться в случайный параллельный поиск. Если N мало, то ГА работает быстро, но при этом увеличивается опасность преждевременной сходимости к локальному экстремуму. Большая мощность популяции увеличивает генофонд, но процесс поиска замедляется. Обычно полагают N [30;200] . На разных этапах работы ГА оптимальное значение N может быть различным. На начальном этапе N должно быть большим, а на заключительном N можно уменьшить. Большую роль играют также вид генетических операторов, которые представлены в следующем разделе. Кроме этого, не менее важны значения вероятностей кроссинговера и мутации Pc и Pm . 29 30 Для оптимизации, особенно мультимодальных функций, наиболее существенными являются две характеристики ГА: - способность сходиться к оптимуму (локальному или глобальному) после нахождения области, содержащей этот оптимум; - способность находить новые области в пространстве решений в поисках глобального оптимума. Баланс между этими характеристиками ГА в значительной степени определяется значениями вероятности Pc и Pm , типом используемых генетических операторов (прежде всего кроссинговера). Увеличение значений Pc и Pm ведет к расширению пространства поиска. Обычно используют следующие значения вероятностей: Pc  0.5;1 и Pm  0.001;0.05 . В адаптивных генетических алгоритмах изменяются, вероятности кроссинговера и мутации Pc и Pm . прежде всего, 1.7. Преимущества и недостатки генетических алгоритмов 1.7.1. Концептуальная простота Основным преимуществом ГА является их концептуальная простота. Рассмотрим снова блок-схему ГА, представленную на рис.1.1. Основными шагами алгоритма являются: инициализация, оценка качества решения с помощью фитнесс-функции, итеративное изменение популяции путем отбора особей и применения генетических операторов. Отметим, что здесь не важна высокая точность оценки качества потенциальных решений – необходимо знать прежде всего их ранг (номер позиции по качеству решения). Информация о значениях градиента целевой функции здесь не нужна. Через ряд итераций (поколений) популяция (множество потенциальных решений проблемы) может сойтись асимптотически к оптимальному решению. Эффективность ГА зависит от способа кодирования решения, используемых генетических операторов, включая отбор особей, и начальной инициализации популяции. 1.7.2. Широкая применимость ГА могут быть использованы при решении любой проблемы, которая может быть сформулирована как задача оптимизации. Они требуют разработки (или выбора) структуры данных для представления потенциального решения, показателя качества для оценки потенциального решения и генетических операторов, порождающих новые решения из старых. Пространство возможных решений может быть разбито на различные области, которые могут включать недостижимые зоны и зоны возможных изменений. Способ представления решения обычно выбирается инженером-разработчиком на основании его интуиции и опыта. В этом смысле процедура выбора кодирования потенциального решения независима в отличие от обычных численных методов, где, как правило, допускаются 30 31 только непрерывные значения из определенного диапазона. Представление решения должно позволять генетическим операторам при изменении решений сохранять поведенческую связь между родителями и потомками. Небольшие изменения в структуре данных родителя должны вести к небольшим изменениям свойств потомков и наоборот, большие изменения у родителей должны вызывать значительные изменения свойств потомков, что должно способствовать эффективному поиску решения в пространстве поиска. Множество возможных изменений может регулироваться с помощью эффективного размера шага изменения в пространстве поиска, который может регулироваться разработчиком (или даже адаптироваться автоматически). Такой гибкий подход позволяет использовать по сути одну и ту же процедуру при решении задач как численной, так и комбинаторной оптимизации (в частности, целочисленной оптимизации и т.п.). 1.7.3. Менее жесткие требования при решении реальных задач Реальные задачи оптимизации часто: 1) накладывают нелинейные ограничения; 2) требуют платежной функции, не связанной с наименьшей квадратичной ошибкой; 3) включают наличие шумов или случайных выбросов, которые не позволяют применять классические методы оптимизации [7]. Целевые функции для реальных проблем часто мультимодальны и градиентные методы сходятся быстро к локальным экстремумам, которые могут давать неудовлетворительные решения. Для простых задач, где поверхность отклика, например, является строго выпуклой, генетические алгоритмы проигрывают классическим по эффективности. Эксперименты показали, что для мультимодальных функций ГА дают лучшие результаты. В случае нелинейных ограничений классические методы даже при выпуклой поверхности могут давать некорректные результаты. Напротив, эволюционные методы могут непосредственно учитывать произвольные линейные и нелинейные ограничения. 1.7.4. Потенциальное использование априорных знаний и гибридизация с другими методами При решении конкретной проблемы всегда целесообразно учесть в алгоритме проблемно-ориентированные априорные знания [7]. Специализированные алгоритмы, учитывающие такую информацию (но имеющие ограниченную область применения), как правило, существенно превосходят по характеристикам неспециализированные методы. Эволюционные алгоритмы по своей структуре легче позволяют учитывать априорные знания. Это может быть выражено, например, в виде специальной структуры данных для представления решений или специальных проблемноориентированных генетических операторов. Часто такая информация включается в фитнесс-функцию (например, физические или химические 31 32 свойства вещества), что позволяет сфокусировать поиск решения в пространстве поиска. Генетические алгоритмы могут комбинироваться с другими более традиционными методами. Известны работы, где на первом этапе оптимизации используются генетические алгоритмы совместно с градиентным методом, который применяется на заключительном этапе, когда уже найдена «зона интереса». Эти алгоритмы могут применяться совместно и параллельно. Отметим, что начальная популяция потенциальных решений может быть получена путем применения, например, жадных алгоритмов, а не эволюционных методов. Генетические алгоритмы часто используются для оптимизации и обучения искусственных нейронных сетей или нечетких продукционных систем. В этом случае часто удается преодолеть ограничения, связанные с традиционными подходами. 1.7.5. Параллелизм Эволюция является высоко параллельным процессом, поскольку популяция состоит из множества особей, которые развиваются параллельно. Это позволяет расширить возможности применения эволюционных вычислений для решения все более сложных задач. Отметим, что основные вычислительные ресурсы в генетических алгоритмах используются при оценке значений фитнесс-функций, которые для различных особей могут выполняться параллельно, а последовательной является только процедура отбора. Поэтому эволюционные методы естественно реализуются в многопроцессорных распределенных компьютерных системах, которые в настоящее время все шире применяются в различных областях науки и техники и даже на бытовом уровне в многоядерных процессорах. В действительности при решении некоторых задач на распределенных вычислительных системах время решения в идеале может быть обратно пропорционально числу используемых задач. Это создает благоприятные условия для решения сложных задач высокой размерности за разумное время с помощью генетических алгоритмов. 1.7.6. Устойчивость к динамическим изменениям Традиционные методы оптимизации неустойчивы к динамическим изменениям окружающей среды и часто требуют полного рестарта при таких изменениях для получения адекватного решения. Напротив, эволюционные алгоритмы могут быть использованы для адаптации потенциальных решений к изменившимся условиям. Полученная на момент изменения популяция дает базис для дальнейшего улучшения решений и в большинстве случаев нет необходимости проводить случайную реинициализацию. 1.7.7. Способность к самоорганизации Большинство классических методов требуют начальной установки соответствующих параметров алгоритмов. Это также относится и к 32 33 генетическим алгоритмам, которые зависят от множества параметров, таких как мощность популяции, вероятности кроссинговера и мутации, шаг мутации и т.п. Однако в эволюционных алгоритмах легче ввести самоадаптацию, когда в процессе поиска решения указанные параметры оптимизируются. 1.7.8. Решение проблем, для которых отсутствует опыт решений Возможно, самым большим преимуществом генетических алгоритмов является их способность исследовать проблемы, для которых нет экспертов и соответствующего опыта решений. Следует отметить, что экспертные оценки достаточно часто используются при решении трудно формализуемых задач, но они иногда дают менее адекватные решения, чем автоматизированные методы. Существуют определенные проблемы с получением знаний у экспертов: они могут не согласиться на это, могут быть неквалифицированными, могут быть несовместимыми и просто ошибаться. Исследования по искусственному интеллекту в настоящее время дали ряд интересных результатов, каждый из которых позволяет эффективно решать свой класс задач (например, хорошо играть в шахматы, или распознавать изображения символов и т.п.). Но большинство этих узких приложений требуют участия человека. Эти методы могут эффективно решать некоторые сложные проблемы, требующие высокого быстродействия, но они не могут конкурировать с человеческим интеллектом - «Они решают проблемы, но они не решают проблему как решать проблемы». Напротив, эволюционные алгоритмы дают метод решения проблемы, как решать проблемы при отсутствии экспертов (человеческого опыта) [7]. 1.7.9. Недостатки ГА Естественно ГА не свободны от недостатков. К ним можно отнести прежде всего следующие. Конфигурация ГА для решения сложных реальных задач не очевидна. Для решения конкретной задачи необходимо выбрать или разработать представление (кодирование) потенциального решения. Существует также проблема определения фитнесс-функции. Есть проблема выбора параметров ГА, таких как мощность популяции, вероятности генетических операторов и т.д. Нет эффективных критериев окончания работа алгоритма. ГА не могут использовать информацию о градиентах, что уменьшает их эффективность для классических задач. ГА не эффективны для гладких унимодальных (с одним экстремумом) функций. ГА не эффективны при поиске локальных экстремумов. ГА требуют достаточно больших вычислительных ресурсов. При решении мультимодальных задач бывают случаи преждевременной сходимости к локальным экстремумам и поэтому в общем случае не гарантируют нахождение глобального экстремума. Ключевые термины: 33 34 Простой генетический алгоритм, генетические операторы, фитнессфункция, схема, фундаментальная теорема ГА, строительные блоки Контрольные вопросы 1. Каковы “источники” ГА? 2. Какие генетические операторы используются в ГА? 3. Какую роль в ГА играет оператор репродукции (ОР)? 4. Опишите реализацию ОР в виде колеса рулетки и приведите пример его работы. 5. Придумайте другую реализацию ОР. 6. Опишите одноточечный оператор кроссинговера (ОК) и приведите пример его работы. 7. Предложите другую реализацию ОК. 8. Какую роль играет оператор мутации (ОМ)? 9. Опишите ОМ и приведите пример его работы. 10. Предложите другую реализацию ОМ. 11. Каковы основные параметры ГА? 34 35 Список литературы 1. Holland J.P. Adaptation in Natural and Artificial Systems. An Introductionary analysis with application to biology? Control and Artificial Intelligence.University of Michigan, 1975,210 p. 2. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning.-Addison-Wesley, reading, MA.-1989. 3. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. -М.: Физматлит.-2006.-319с. 4. Скобцов Ю.А.. Основы эволюционных вычислений.- Донецк: ДонНТУ, 2008.- 326с. 5. Michalevich Z. Genetic Algorithms + data structures=Evolution Programs.Springer.-1999. 6. Рутковская Д., Пилинский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы. -М: Горячая линия, 2004.452с. 7. Sivanandam S.N., Deepa S.N. Introduction to genetic algorithms. –Berlin, Heidelberg: Springer- Verlag, 2008. 8. Wolpert D.H., Macready W.G. No free lunch theorems for search // Operations research: Santa Fe Institute, 1995. 9. Wolpert D. H., Macready W.G. 1996. No Free Lunch Theorems for Search Technical.- Report SFI-TR-95-02-010.- Sania Fe Instituie. 35 36 2. Генетические алгоритмы для задач комбинаторной оптимизации До сих пор рассматривалось применение ГА, в основном, при решении задачи численной оптимизации при поиске экстремумов функции. Но в настоящее время ГА используются больше для решения задач комбинаторной оптимизации, которым посвящена подавляющая часть публикаций. Базовой задачей комбинаторной оптимизации является задача коммивояжера, для которой отрабатываются новые методы решения задач данного типа. Поэтому большая часть раздела посвящена решению задачи коммивояжера с помощью ГА на основе различных способов кодирования потенциальных решений и проблемно-ориентированных генетических операторов кроссинговера. Однако сначала рассматриваются задачи об укладке рюкзака и покрытии множества, которые допускают использование простого (классического) ГА [1-3]. 2.1. Задача об укладке рюкзака Эта задача имеет следующую неформальную простую постановку [4,5]. Имеется рюкзак объемом C и n различных предметов. Каждый предмет i имеет известный объем Wi и стоимость Pi ( i  1,..., n ). В рюкзак можно положить целое число различных предметов. Нужно упаковать рюкзак так, чтобы полная стоимость уложенных предметов была максимальной, а их общий объем не превышал заданный объем С. Форма предметов здесь не учиты. Формальная постановка задачи: для данного множества весов Wi , стоимостей Pi и объема C надо найти двоичный вектор 1, если предмет помещается в рюкзак,  0 в противномслучае, X= (x1,…, xn), где xi   и при этом должно выполняться условие: n V  Wi  C i 1 и n  P  max . i 1 i Так как решение задачи можно представить двоичным вектором X= (x1,…, xn), то очевидно при его поиске можно применить простой ГА со стандартными операторами скрещивания и мутации. Но при этом на каждом шаге итерации надо следить за тем, чтобы новые решения, полученные в результате скрещивания или мутации, удовлетворяли требуемому ограничению V  C . В случае невыполнения ограничения «неправильное» потенциальное решение должно быть уничтожено, что ведет к сокращению популяции. В качестве фитнесс-функции в простейшем случае можно взять n P X    xi  Pi , но в этом случае, как указано выше, есть проблемы с i 1 неправильными решениями. 36 37 Данная задача относится к классу задач с ограничениями, при решении которых применяются следующие подходы [4,5]: 1) введение в фитнессфункцию дополнительного штрафа; 2) использование алгоритмов “восстановления” некорректных решений. 1) В первом случае в фитнесс-функцию вводится дополнительная штрафная функция, которая для неправильных решений дает большие отрицательные значения ЦФ. При этом задача с ограничениями трансформируется в задачу без ограничений путем назначения штрафа для некорректных решений. Фитнесс-функция для каждой особи может быть определена следующим образом n f ( X )   xi  Pi  Pen ( X ) . i 1 Разработано множество методов назначения штрафных значений, из которых ниже рассмотрено только три вида, когда рост значения штрафной функции относительно степени нарушения ограничения имеет логарифмический, линейный и квадратичный характер: n a) Pen ( X )  log 2 (1    ( xi  Wi  C )), i 1 n б) Pen ( X )    ( xi  Wi  C ), i 1 n в) Pen( X )  (   ( xi Wi  C ))2 . i 1 Здесь для всех трех случаев   max{Pi / wi } . 1i  n 2) Второй подход к решению задач с ограничениями основан на специальных алгоритмах “восстановления” некорректных решений. Следует отметить, что многие алгоритмы восстановления требуют значительных вычислительных ресурсов, и полученные решения иногда требуют адаптации к конкретным практическим приложениям. В этом случае в качестве фитнесс-функции используется n f ( X ' )   xi ' Pi , где вектор X  – восстановленная версия исходного вектора X. i 1 Здесь следует отметить, по крайней мере, два аспекта. Во-первых, можно использовать различные алгоритмы восстановления. Во-вторых, восстановленные особи могут замещать только некоторую часть исходных особей в популяции. Процент замещаемых особей может варьироваться от 0% до 100% и его значение является важнейшим параметром метода восстановления. В некоторых работах отмечается, что наилучшие результаты получаются при 5%, во всяком случае, лучше, чем в двух крайних случаях – 0% (без замещения) и 100% (любая восстановленная особь заменяет исходную). Ниже приведен простой алгоритм восстановления. Восстановление(X) { 37 38 переполнение_рюкзака=false; X’=X; n if ( f ( X ' )   xi 'Wi  C ) i 1 then переполнение_рюкзака=true; while(переполнение_рюкзака) { i=выбор предмета из рюкзака; // удаление выбранного предмета из рюкзака; x' i  0 ; n if ( f ( X ' )   x'i Wi  C ) i 1 then переполнение_рюкзака=false; } } При этом используются два основных способа выбора объекта: а) случайный выбор объекта из рюкзака; б) “жадное восстановление”, при котором вначале все предметы сортируются в порядке убывания их стоимости Pi и на каждом шаге для удаления выбирается предмет минимальной стоимости (из имеющихся в рюкзаке). 3) Третий подход к решению задач с ограничениями использует специальное отображение (декодирование) особей, которое гарантирует генерацию допустимого решения (с учетом ограничений), или используют проблемно-ориентированные генетические операторы, сохраняющие корректность решения. Рассмотрим один из возможных вариантов алгоритма декодирования, который основан на кодировании решения вектором целых чисел, так называемом «упорядоченном представлении» (ordinal representation), подробно описанном в разделе 3.3.2. Здесь каждая хромосома кодируется вектором e целых чисел, где i-я компонента вектора – есть целое число в диапазоне от 1 до n-i+1. “Упорядоченное представление” использует для ссылок (базовый) список предметов L. Вектор e фактически содержит указатели на базовый список L. Декодирование вектора осуществляется путем выбора соответствующего предмета из текущего списка и удаления его из базового списка. Например, при базовом списке предметов L=(1,2,3,4,5,6) текущий вектор e=(4,3,4,1,1,1) декодируется в следующую последовательность предметов: 4, 3, 6, 1,2, 5. Первым в рюкзак включается четвертый элемент списка L - 4, который устраняется из L. Далее в рюкзак включается третий элемент из текущего списка L. Затем включается 6 четвертый элемент текущего L и т.д. Подробнее описание этого представления и выполнение кроссинговера на нем описано в разделе 2.3.2. В данном методе хромосома может интерпретироваться как стратегия 38 39 (порядок) включения предметов в решение. Отметим, что основным достоинством данного кодирования хромосомы является то, что на нем работает одноточечный кроссинговер. То есть для двух допустимых решений –родителей кроссинговер порождает также допустимое решение–потомок. Оператор мутации при данном представлении выполняется путем замены iго гена (целочисленной компоненты вектора) на случайное целое число из диапазона [1,…,n-i+1]. Алгоритм декодирования представлен ниже. Декодирование(X) { генерация списка предметов L; i=1; Сумма_весов=0; Суммарная_стоимость=0; While( i  n ) { j= xi ; удаление j-го предмета из списка L; if( сумма _ весов  W j  C ) then { Сумма_весов= Сумма_весов + W j ; Суммарная_стоимость= Суммарная_стоимость + Pj ; } i=i+1; } } Очевидно, что представленный алгоритм зависит от способа генерации списка предметов L. Обычно используются два метода генерации этого списка: а) список предметов L генерируется в том порядке, в котором предметы расположены во входном файле (как правило, случайно); б) список предметов L генерируется в порядке убывания их стоимостей (жадный алгоритм). Декодирование вектора X выполняется на основе отсортированного вектора. Например, x 25 интерпретируется как 25-й предмет текущего списка L. Задача об укладке рюкзака в различных вариантах имеет многочисленные практические приложения. Например, к ней можно свести оптимизацию загрузки транспорта и т.п. 2.2. Задача о покрытии Задано множество элементов S и множество подмножеств F  {F1 ,..., Fn } этого множества S . Необходимо найти минимальное число подмножеств из 39 40 F таких, чтобы объединение этих подмножеств содержало все элементы множества S . Задача имеет простую экономическую интерпретацию: пусть, например, имеется некоторое количество клиентов и для их обслуживания необходимо выбрать некоторое количество сервисных центров. Требуется найти минимальное число центров, способных обслуживать всех клиентов. Очевидно, здесь решение можно также представить двоичным вектором X= (x1,…, xn), где xi=1 , если подмножество Fi входит в покрытие; xi=0, если Fi не входит в покрытие; и при этом  xi Fi  S , i 1,..., n n x i 1 i  min Поскольку решение задачи, как было показано выше, представляется двоичным вектором, то при его поиске можно использовать простой ГА со стандартными операторами кроссинговера и мутации. 2.3. Задача коммивояжера Напомним неформальную постановку этой классической задачи. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по одному разу в некотором порядке все города и вернуться в исходный город. На рис.2.1 приведен пример задачи для четырех городов. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим? 2 1 4 3 Рис.2.1. Задача коммивояжера В формальной постановке задачи коммивояжера (ЗК): имеется полный взвешенный ориентированный граф G без петель с множеством вершин N={1,2,…,n}; веса всех дуг неотрицательны; в этом графе требуется найти гамильтонов цикл с минимальной длиной. Исходная информация по ЗК представляется в виде n  n матрицы S   si , j  , si , j  вес дуги (i,j) графа G, i  1, n , j  1, n , i  j ; все элементы главной диагонали нулевые sii  0 (но в некоторых постановках полагаются sii   ). Обычно sij интерпретируется 40 41 как расстояние между городами i и j . С учетом других возможных интерпретаций на матрицу S требование симметричности не налагается. Например, в случае интерпретации sij как стоимости проезда, в общем случае может быть sij  s ji . В общем случае не считается обязательным и выполнение неравенства треугольника s ij  s jk  s ik . Тур коммивояжера может быть описан циклической перестановкой t=(j1,j2,..,jn,j1), причём все j1 ,..., jn – попарно различны; повторяющийся в начале и в конце номер города j1, показывает, что перестановка циклическая. Пространством поиска решений этой задачи является множество перестановок n городов. Любая простая (одиночная) перестановка n городов даёт решение, являющееся полным туром из n городов. Оптимальным решением является перестановка, которая даёт минимальную стоимость тура. Очевидно, размерность пространства поиска для несимметричной задачи равна (n-1)!. Известно, что эта задача является NP – полной, т.е. переборной. Она имеет многочисленные практические приложения, в которых число “городов” может быть достаточно большим. Например, при производстве сложных деталей задача сверления отверстий может иметь сотни и тысячи “городов”. При производстве СБИС возникают задачи (например, по внесению примесей в полупроводник) с числом “городов” около миллиона. За последние десятилетия разработано достаточно много алгоритмов решения этой задачи, дающих субоптимальное решение. В последнее десятилетие эта задача является базовой для исследования ГА в области комбинаторной оптимизации. Очевидно, что двоичное представление тура при решении ЗК нецелесообразно. Действительно если мы интересуемся оптимальной перестановкой городов, т.е. (i1,i2, … , in) и используем двоичное представление в виде одного бинарного вектора, то изменение даже в одном бите двоичного кода перестановки может дать двоичный вектор, не принадлежащий к области решения, т.е. не являющейся перестановкой n городов. Для решения ЗК с помощью генетических алгоритмов разработаны специальные методы представления (кодирования) решений и соответствующие проблемно-ориентированные генетические операторы [24]. В основном используются три способа представления тура при решении ЗК с использованием ГА: 1) представление порядка; 2) представление соседства; 3) представление путей. Для каждого из этих представлений разработаны свои “генетические” операторы. Оператор мутации относительно легко определить на этих представлениях в виде одиночной перестановки соседних городов в туре. Поэтому в дальнейшем мы, в основном, рассмотрим операторы кроссинговера. 2.3.1. Упорядоченное представление. 41 42 В этом случае тур представляется списком из n городов, где i-й элемент списка имеет номер от 1 до n-i+1. При этом используется базовый упорядоченный список городов L, который служит для ссылок упорядоченного представления. Фактически мы рассматривали этот метод кодирования решения при решении задачи об укладке рюкзака. Рассмотрим его на конкретном примере тура T= (1-2-4-3-8-5-9-6-7), для которого упорядоченный список L = (1 2 3 4 5 6 7 8 9). Тогда данный тур при этом упорядоченном списке представляется следующим списком ссылок e=(1 1 2 1 4 1 3 1 1), который интерпретируется следующим образом. Здесь жирным курсивом выделен текущий указатель в списке е. Первый номер из списка е равен 1, поэтому помещаем в тур 1-й город из базового списка L, удаляем его из L и сдвигаем указатель по e. Тогда получаем: тур T1=(1), базовый список L1= (2 3 4 5 6 7 8 9) , указатель e=(1 1 2 1 4 1 3 1 1). Следующий номер по указателю e также равен 1, поэтому снова помещаем в тур 1-й город из базового списка L, удаляем его из L и сдвигаем указатель по e. В результате получаем : текущий тур T2=( 1-2), L1 = (3 4 5 6 7 8 9) и указатель в e сдвигается на третью позицию е = (1 1 2 1 4 1 3 1 1). Следующий номер списка е равен 2, поэтому мы берем и удаляем 2-й город из текущего базового списка L и добавляем его в тур и передвигаем указатель по е. Имеем: текущий тур T3=(1-2-4), L = (3 5 6 7 8 9), е = (1 1 2 1 4 1 3 1 1). Продолжая этот процесс, в результате декодирования по данному коду e=(1 1 2 1 4 1 3 1 1), базовому списку L = (1 2 3 4 5 6 7 8 9) будет построен тур T= (1-2-4-3-8-5-9-6-7) . Основное преимущество упорядоченного представления в том, что в этом случае работает классический кроссинговер (над векторами целых чисел). То есть для двух допустимых решений кроссинговер производит два допустимых решения – потомка. Например, для родителей e1 = (1 1 2 1 | 4 1 3 1 1) и e2 = (5 1 5 5 | 5 3 3 2 1), которые соответствуют турам T1=(1-2-4-3-8-5-9-6-7) и T2=(5-1-7-8-9-4-6-3-2) , имеем следующих потомков при скрещивании О1 = (1 1 2 1 5 3 3 2 1) и О2 = (5 1 5 5 4 1 3 1 1), которые представляют туры T3=(1-2-4-3-9-7-8-6-5) и T4=(5-1-7-8-6-2-9-3-4). Очевидно, что частичные туры слева от точки кроссинговера не изменяются, в тоже время частичные туры справа от нее разрываются случайным образом (сохраняя корректность решения). К сожалению, машинные эксперименты по решению ЗК на основе этого представления 42 43 решений с использованием классического кроссинговера показывают посредственные результаты [4]. 2.3.2. Представление соседства В этом случае тур представляется списком соседних городов. Город j находится в позиции i если и только если в туре после города i посещается город j, что показано на рис.3.2. j i Рис.2.2. Следование городов в туре Например, вектор n1=(2 4 8 3 9 7 1 5 6) представляет следующий тур T1=(1-2-4-3-8-5-9-6-7). При этом любой тур имеет единственное представление списком соседства. Однако некоторые «списки соседей» могут представлять “неправильные” туры. Например, список соседства n2=(2 4 8 1 9 3 5 7 6) содержит “частичный” тур T2=(1-2-4-1). Поэтому представление списком соседей не поддерживает классический оператор кроссинговера, поскольку при перестановке частей списков могут получаться неправильные (“частичные”) туры. В этом случае необходим некоторый алгоритм восстановления полного тура. Для данного способа кодирования решения были предложены и исследованы 3 основных оператора кроссинговера: 1) обмен ребер (дуг) графа; 3) обмен подтуров; 3) эвристический кроссинговер [2-4]. Далее рассмотрим их детально. 1) Обмен ребер. Этот тип кроссинговера строит потомка (случайным) выбором ребра (пары городов i-j ) из первого родителя, затем выбором соответствующего ребра из второго родителя и т.д. Оператор наращивает тур выбором ребер из различных родителей. Если новое ребро (взятое у одного из родителей) образует преждевременный (частичный) цикл в текущем (ещё не полном) туре, то оператор выбирает (случайно) вместо этого ребра одно из оставшихся ребер, которое не дает преждевременного цикла. Например, для 2-х родителей n1 = (2 3 8 7 9 4 1 5 6), представляющего тур T1=(1-2-3-8-5-9-6-4-7-1), и n2 = (7 5 1 6 9 2 8 4 3) , представляющего тур T2=(1-7-8-4-6-2-5-9-31), получаем следующего потомка 1 = (2 5 8 7 9 4 3 1 6). Здесь произведен обмен (случайный) ребер 3  5 во второй позиции, далее при попытке обмена 8  1 в седьмой позиции возникает конфликт (два ребра входят в 8), поэтому случайно выбирается 3 в позиции 7 ( из оставшихся 6, 1, 3), 1 – в позиции 8 и 6 в позиции 9. В результате порождается потомок 1, который соответствует туру T3=(1-2-5-9-6-4-7-3-8-1). 2) Обмен подтуров. 43 44 Этот оператор строит потомки путём выбора (случайной длины) подтура из первого родителя, затем выбора подтура (опять случайной длины) из второго родителя и их обмена. Как и ранее, в случае конфликта оператор случайно выбирает другое ребро (город) из не вошедших в построенный тур. 3) Эвристическое скрещивание. Данный оператор строит потомка случайным выбором города в качестве начальной точки для формирования тура. Затем сравниваются два ребра, исходящие из этого города, имеющихся в двух родителях, и из них выбирается лучшее с меньшей стоимостью. Полученный город (в него входит выбранное ребро на предыдущем этапе), используется в качестве начальной точки при выборе следующего ребра и т.д. Как и ранее, в случае возникновения преждевременного цикла, следующий город выбирается случайно из городов, еще не вошедших в текущий тур. Известна следующая модификация этого оператора. Если оптимальное (с меньшей стоимостью) ребро дает преждевременный цикл в потомке, то проверяется альтернативное ребро (с большей стоимостью) на генерацию преждевременного цикла. Если это ребро не генерирует цикл, то оно включается в тур, иначе выбирается минимальное из q ребер (где q –параметр пула выбора) случайно выбранных из оставшихся городов. Преимущество этого кодирования в том, что в этом случае анализ схем (шаблонов) можно проводить по аналогии с двоичным случаем. Например, схема (   3  7   ) представляет множество всех туров с ребрами (4-3) и (6-7). Однако основной недостаток этого представления в весьма посредственных результатах тестовых задач для всех трех рассмотренных операторов. Кроссинговер обмена ребер часто разрывает хорошие туры при обмене ребер родителей. Кроссинговер обмена подтуров даёт лучшие результаты, чем предыдущий, так как “отношение разрыва” здесь меньше. Эвристический оператор даёт несколько лучшие результаты за счет учета стоимости исходящих ребер и локального выбора лучшего варианта из двух возможных. Однако эксперименты показывают также посредственные результаты [4]. 2.3.3. Представление путей. Это представление, возможно, самое естественное для тура. Например, тур (5-1-7-8-9-4-6-2-3) представляется просто упорядоченным списком (5 1 7 8 9 4 6 2 3) городов, входящих в тур. Для данного представления были определены и исследованы три типа кроссинговера [2-4]: 1) частично соответствующий (partially-mapped - РМХ); 2) упорядоченный ОК (order - ОХ); 3) циклический ОК (cycle - CХ). Рассмотрим их по порядку. 44 45 Частично соответствующий ОК (РМХ) строит потомок путем выбора последовательности тура из одного родителя и сохранения порядка и позиции городов из другого родителя насколько это возможно. Подпоследовательность из тура выбирается случайно с помощью двух “секущих” точек, которые служат границами для операции обмена. Например, для родителей Р1=(1 2 3 | 4 5 6 7| 8 9) и Р2 = (4 5 2 | 1 8 7 6 | 9 3) потомок строится следующим образом. Сначала производим обмен выделенными подтурами и в результате получаем Т1 = (X X X | 1 8 7 6 | X X) и T2 = (X X X | 4 5 6 7 | X X), где ‘X’ означает еще незаполненную позицию (допускающую произвольное значение). Этот обмен определяет также отображение 1  4,8  5,7  6 . Далее (вместо ‘Х’) вставляем города из исходных родителей, для которых нет конфликтов (не образуются преждевременный цикл): O1 = (X 2 3 | 1 8 7 6 | X 9), O2 = (X X 2 | 4 5 6 7 | 9 3). Далее первый ‘Х’ в О1, заменяем на ‘4’ согласно отображению 1  4 . Аналогично второй ‘Х’ в потомке О1 заменяется ‘5’, и во втором потомке О2 оставшиеся неопределенные позиции ‘Х’ заменяются соответственно на 1 и 8. В результате получаем два потомка: О1 = (4 2 3 | 1 8 7 6 | 5 9) и О2 = ( 1 8 2 | 4 5 6 7 | 9 3). Упорядоченный ОК строит потомок выбором подтура из одного родителя и сохранением относительного порядка городов из другого родителя. Например, для родителей P1 = (1 2 3 | 4 5 6 7 | 8 9), P2 = (4 5 2 | 1 8 7 6 | 9 3) потомок строится следующим образом. Сначала сегменты между двумя секущими точками копируется в потомки: О1 = (X X X | 4 5 6 7 | X X), О2 = (X X X | 1 8 7 6 | X X). Далее, в первом родителе, начиная со второй секущей точки, копируются города из другого родителя, пропуская уже присутствующие в построенном подтуре. По достижению конца списка этот процесс продолжается с первой позиции и до первой точки сечения (по кольцу). Для нашего примера после второй точки сечения во втором родителе мы имеем следующую последовательность: 9 – 3 – 4 – 5 – 2 – 1 – 8 – 7 – 6. Удаляем из нее города 4, 5, 6, 7, поскольку они уже есть в первом потомке, и в результате получаем последовательность 9 – 3 – 2 – 1 – 8. Ее мы помещаем в первый потомок, начиная со второй точки сечения (по кольцу) и получаем потомок O1 = (2 1 8 | 4 5 6 7 | 9 3). Аналогично получаем второго потомка O2 = (3 4 5 | 1 8 7 6 | 9 2). Оператор кроссинговера ОХ опирается на то, что при представлении тура прежде всего важен порядок городов, например, два тура (9–3–4–5–2– 1–8–7–6) и (4–5–2–1–8–7–6–9–3) идентичны. 45 46 Циклический ОК строит потомки таким образом, что каждый город вместе со своей позицией идет от одного из родителей. Например, для родителей Р1 = (1 2 3 4 5 6 7 8 9) и Р2 = (4 1 2 8 7 6 9 3 5) сначала получаем путем выбора первого города из родителя O1= (1X X X X X X X X). Выбор следующего города определяет текущая позиция второго родителя. В нашем примере это город 4, что дает O1= (1 X X 4 X X X X X). Город 4 в свою очередь имплицирует город 8 (из второго родителя), что дает O1= (1 X X 4 X X X 8 X). Аналогично получаем города 3, 2 в O1= (1 2 3 4 X X X 8 X). Здесь мы вынуждены прервать этот процесс, так как выбор 2  1 ведет к преждевременному циклу. Поэтому оставшиеся города берутся из другого родителя P2 (с сохранением порядка) и в результате получаем потомковO1 = (1 2 3 4 7 6 9 8 5 ) и О2 = (4 1 2 8 5 6 7 3 9). Таким образом, оператор ОК СХ сохраняет абсолютные позиции потомков и родителей. Ключевые термины: Комбинаторная оптимизация, задаче об укладке рюкзака, задача о покрытии, задача коммивояжера, задача о сокращении диагностической информации, кодирование потенциальных решений, проблемноориентированные генетические операторы. 1. 2. 3. 4. 5. 6. 7. 8. Контрольные вопросы При решении каких задач комбинаторной оптимизации может быть использован простой ГА с двоичным кодированием хромосом? Какие модификации необходимы для эффективного использования простого ГА для решения задачи укладки рюкзака? Какие виды штрафных функций могут быть использованы в фитнессфункции при решении задачи укладки рюкзака? Выполните программную реализацию простого ГА на одном из языков программирования для решения задачи укладки рюкзака с введением в фитнесс-функцию штрафной функции. Исследуйте эффективность ГА в зависимости от вида штрафной функции. В чем суть алгоритма восстановления при решения задачи укладки рюкзака? Выполните программную реализацию простого ГА на одном из языков программирования для решения задачи укладки рюкзака с использованием алгоритма восстановления. Выполните программную реализацию простого ГА на одном из языков программирования для решения задачи укладки рюкзака с использованием алгоритма декодирования. Как может быть использован простой ГА с двоичным кодированием хромосом для решения задачи о покрытии? 46 47 9. Почему неэффективно двоичное кодирование хромосомы при решении задачи коммивояжера? 10. Опишите основные виды недвоичного представления хромосомы для задачи коммивояжера. 11.Опишите “представление соседства” и проблемно-ориентированные операторы кроссинговера: обмен ребер, обмен туров, эвристический кроссинговер. 12. Как может быть выполнен оператор мутации на представлении соседства? 13. Опишите “упорядоченное представление” и укажите какой тип оператора кроссинговера может на нем использоваться. 14.Опишите “представление путей” и проблемно-ориентированные операторы кроссинговера: частично соответствующей ОК (РМХ), упорядоченный ОК (ОХ), циклический ОК (СХ). Список литературы 10. Holland J.H. Adaptation in Natural and Artificial Systems. An Introductory Analysis with Application to Biology - Control and Artificial Intelligence. University of Michigan, -1975.-210 p. 11. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning.-Addison- Wesley, MA.-1989. 12. Гладков Л.А., Курейчик В.В, Курейчик В.М. Генетические алгоритмы. -М.:Физматлит.-2006.-319с. 13. Скобцов Ю.А. Основы эволюционных вычислений.- Донецк: ДонНТУ, 2008.- 326 с. 14. Michalevich Z . Genetic Algorithms + data structures=Evolution Programs. - Springer.-1999. 15. Тестовые наборы для задачи коммивояжера [Электронный ресурс]. – Режим доступа: http://www.tsp.gatech.edu//world/countries.html 16. Тестовые наборы для задачи коммивояжера [Электронный ресурс]. – Режим доступа: http://www.iwr.uni-heidelberg.de/groups/comopt/ software/TSPLIB95/tsp/ 17. Барашко А.С., Скобцов Ю.А., Сперанский Д.В. Моделирование и тестирование дискретных устройств. – Киев: Наукова думка, 1992. 18. Миронов С.В., Сперанский Д.В. Генетические алгоритмы для сокращения диагностической информации //Автоматика и телемеханика.-2008.-№7.С.146-156. 19. Brgles F., Brayan D., Kazminski K. Combinational profiles of sequential benchmark circuits // Proceed. of 1989 Intern. Symposium on Sequential Circuits –Portland, OR, USA, 1989.- P.1929-1934. 20. Скобцов Ю.А., Сперанский Д.В., Скобцов В.Ю. Моделирование, тестирование и диагностика цифровых устройств. – М.: Национальный Открытый Университет «ИНТУИТ», 2012. 47 48 3. Модификации генетических алгоритмов В предыдущих разделах, в основном, рассмотрена классическая реализация простого ГА. В настоящем разделе описаны модификации ГА. Прежде всего это различные модификации и обобщения для каждого функционального блока основной схемы ГА рис. 1.1 раздела 1 без изменения последовательности этих блоков. Описаны различные методы генерации начальной популяции, отбора родителей, разные формы представления потенциальных решений и генетические операторы кроссинговера и мутации, определенные для соответствующего кодирования. Кроме этого, изложены нестационарные ГА с изменяемой мощностью популяции, ниши и адаптивные ГА, где параметры подстраиваются в процессе поиска решения. 3.1. Создание исходной популяции В настоящее время наиболее известными и часто применяемыми на практике являются три способа создания исходной популяции (начального множества решений)[1,2]. Стратегия "одеяла" – формирование полной популяции, содержащей все возможные решения. Например, для n-разрядной хромосомы мы имеем всего 2n вариантов решений, которые составляют полную популяцию. Стратегия "дробовика" - генерация достаточно большого случайного подмножества решений. Стратегия фокусировки - генерация подмножества решений, включающих разновидности одного решения. Первый подход (стратегия «одеяла») практически не реализуем даже для задач средней размерности, вследствие больших вычислительных затрат. Заметим, что при этом подходе начальная популяция не может развиваться, т.к. в ней уже содержатся все возможные решения. Третий способ используется тогда, когда есть предположение, что некоторое решение является вариацией известного значения. В этом случае время поиска оптимального решения существенно сокращается, т.к. алгоритм начинает работу в окрестности оптимума. Чаще всего применяют второй способ. В этом случае в результате эволюции есть возможность перейти в другие подобласти поиска и каждая из них имеет сравнительно небольшое пространство поиска. В целом эффективность ГА, качество решения и дальнейшая эволюция в значительной степени определяются структурой и качеством начальной популяции. На практике часто применяют комбинацию второго и третьего способов. Сначала определяются особи с высокими значениями целевой функции, а затем случайно формируются начальные решения в этих подобластях. 48 49 3.2. Отбор родителей (селекция) ~ Оператор отбора S порождает промежуточную популяцию P t из текущей популяции P t путем отбора и генерации новых копий особей: ~ S Pt   Pt . При отборе конкурентоспособных особей используют целевую (fitness) функцию, как единственно доступный источник информации о качестве решения. Но различные методы отбора родителей по-разному используют эту информацию. Далее мы рассмотрим наиболее распространенные методы отбора родителей [1-3]. 3.2.1. Пропорциональный отбор (метод "рулетки") Данный вид отбора чаще всего используется на практике. При этом особи (решения) отображаются в отрезки линии (или сектора рулетки) таким образом, что их размер пропорционален значению целевой функции для данной особи. Это показано в следующем примере, представленном в табл.3.1 Таблица 3.1 Номер 1 2 3 4 5 6 7 8 9 10 особи Значение 2,0 1,8 1,6 1,4 1,2 1,0 0,8 0,6 0,4 0,2 ЦФ Вероятнос 0,18 0,16 0,15 0,13 0,11 0,09 0,07 0,06 0,03 0,0 ть выбора 2 11 0,0 0,0 Здесь на отрезке [0,1] для каждой особи строятся отрезки, длины которых пропорциональны вероятностям выбора особей, как это показано на рис.3.1. поп ытки 1 2 0,18 3 0,34 4 0,49 5 0,62 6 0,73 7 8 0,82 1 Рис.3.1. Вероятности выбора особей методом рулетки Далее случайно генерируются числа из диапазона [0,1] и в промежуточную популяцию выбираются те особи, в чей «отрезок» попадают эти случайные числа. Таким образом, каждая попытка представляет собой случайное число из отрезка [0,1], в результате чего выбирается особь, соответствующая выбранному отрезку. В данном примере в результате пяти попыток были выбраны в промежуточную популяцию особи 1, 2, 3, 6 и 9. 49 50 Данный метод, несмотря на частое применение, имеет следующие недостатки:  зависимость от положительных значений целевой функции (функция должна для всех особей принимать положительное значение);  метод может использоваться (без модификации) только в задачах максимизации (но не минимизации) функции;  простое добавление очень большой константы к целевой функции может свести способ отбора практически к случайному выбору;  особи с очень маленькими значениями фитнесс-функции слишком быстро исключаются из популяции, что может привести к преждевременной сходимости ГА. Для устранения этих недостатков используют масштабирование оценок значений целевой функции относительно минимального значения в популяции (см. раздел 3.2.8) или метод ранжирования (раздел 3.2.2). Очевидно, что проблема минимизации может быть сведена к задаче максимизации функции и обратно. Поэтому в некоторых реализациях ГА метод рулетки применяется и для поиска минимума функции, что в практических задачах встречается чаще (минимизация затрат, расстояния, погрешности и т.д.) Для приведенного примера можно привести следующую гистограмму вероятностей выбора особей, представленную на рис.3.2. Отметим, что здесь высота "ступенек " различна, в отличие от следующего метода выбора, для которого гистограмма представлена на рис.3.3. 3.2.2. Ранжирование При этом методе особи популяции сортируются (упорядочиваются) согласно значениям целевой функции. Отметим, что здесь вероятность отбора для каждой особи зависит только от ее позиции (номера) в этом упорядоченном множестве особей, а не от самого значения целевой функции. Этот метод отбора более устойчив, чем предыдущий. В основном применяют линейное ранжирование, где вероятность отбора особи ai определяют в соответствии со следующим выражением: 1 i 1  Ps (ai )   a  a  b  , (3.1) N N 1 где 1  a  2 выбирается случайным образом; b  2  a; N – мощность популяции; i – номер особи в упорядоченном списке. Для приведенного примера гистограмма вероятностей выбора особей методом ранжирования, представлена на рис.3.3. Отметим, что здесь высота "ступенек " (разность значений вероятностей отбора- высот столбцов) одинакова, в отличие от предыдущего метода выбора. Иногда применяют нелинейное ранжирование. При этом вероятность отбора также определяется 50 51 номером позиции в упорядоченном множестве особей, но вид функции может быть сложнее. Рис.3.2. Ранжирование особей в операторе селекции методом асимметричного колеса рулетки Рис.3.3. Сортировка особей в операторе селекции методом ранжирования с равным шагом Достоинством метода ранжирования является возможность его применения при поиске как максимумов, так и минимумов функций. Этот метод также не требует масштабирования для предотвращения преждевременной сходимости в отличие от метода рулетки. 3.2.3. Равномерное ранжирование (случайный выбор) 51 52 Здесь вероятность выбора особи определяется выражением: 1 при 1  i     (3.2) Ps (ai )   0 при   i  N  где   N  параметр метода. 3.2.4. Локальный отбор Производится среди особей, которые находятся в некоторой ограниченной среде, где определено отношение соседства. Ранее, фактически, в качестве соседей каждой особи рассматривалась вся популяция. При этом в качестве соседей подразумевается множество партнеров для выполнения операции скрещивания. Соседство можно определить по-разному. Далее рассмотрим типичные отношения соседства, используемые при локальном отборе. 1) Линейное соседство: Рис.3.4. Линейное соседство На рис.3.4 представлен пример линейного соседства. На практике рассматривают полную окрестность (на рис.3.4 вверху показана полная окрестность выделенного элемента с расстоянием d=2) и «полуокрестность» (в правом нижнем углу рисунка показана «полуокрестность» с расстоянием d=1). 2) Двумерное – четырехсвязное соседство. На рис.3.5 представлен пример соседства с 4-связностью (в левом верхнем углу показан полный "крест" выделенного элемента с расстоянием d=1, справа "полукрест" также с расстоянием d=1). 52 53 Рис.3.5. Соседство на четырехсвязной решетке 3) Двумерное – восьмисвязное соседство. Рис.3.6. Соседство на восьмисвязной решетке На рис.3.6 представлен пример соседства с 8-связностью (в левом верхнем углу показан полная "звезда" выделенного элемента с расстоянием d=1, а справа "полузвезда"). Для определения отношения можно также использовать гексагональную решетку с 6-связностью и даже трехмерные структуры. При отборе родителей на первом шаге производится отбор особей случайным образом, или одним из ранее рассмотренных способов. Далее для каждой отобранной особи определяется множество локальных соседей и среди них выбирается партнер для выполнения операции скрещивания. При наличии отношения соседства, между особями возникает эффект «изоляции расстоянием». Очевидно, что чем меньше соседство, тем больше «изоляция расстоянием». Это ограничивает распространение новых решений в популяции. Однако, из-за перекрытия соседних областей, распространение новых вариантов решений все же возможно. Мощность множества соседей определяет скорость распространения информации между особями популяции, способствуя либо быстрому распространению новых решений, либо сохранению имеющегося генофонда в популяции. 53 54 Часто при решении задачи требуется высокая изменчивость, которая поможет избежать преждевременной сходимости в районе локального оптимума. Обычно локальный отбор в малом окружении дает лучшие результаты, чем в большем окружении. В малых и средних популяциях (N<100) для локального отбора рекомендуется двумерная структура типа «полузвезда» с расстоянием d  1 . При большом размере популяции ( N  100 ) лучше использовать большие расстояния d>1 и двумерные структуры с соседством типа «звезда». 3.2.5. Отбор на основе усечения Предыдущие методы отбора в какой то степени заимствованы у (или имеют аналогию с) эволюции естественных популяций. Этот метод не имеет аналогов в естественной эволюции и обычно используется для больших популяций ( N  100 ). При этом сначала отбираемые особи упорядочиваются согласно их значениям целевой функции. Затем в качестве родителей выбираются только лучшие особи. Далее, с равной вероятностью, среди них случайным образом выбирают пары, которые производят потомков. При этом методе используется параметр – порог отсечения T (иногда используется термин интенсивность отбора), показывающий долю (часть популяции), которая отбирается в качестве родителей. Обычно 10%  T  50% . 3.2.6. Турнирный отбор В этом случае все особи популяции разбиваются на подгруппы размера m с последующим выбором в каждой из них особи с лучшим значением фитнесс-функции. Параметром этой процедуры является размер тура m, который принимает значения из диапазона 2  m  N . Используются два способа выбора детерминированный и случайный. При детерминированном способе выбор выполняется с вероятностью, равной 1, в то время как при случайном методе выбор осуществляется с вероятностью меньше 1. Чаще всего популяция разбивается на подгруппы по 2-3 особи в каждой (m=2,3). Рис.3.7 иллюстрирует метод турнирной селекции для подгрупп, состоящих из двух особей. Турнирный метод может быть использован как при максимизации, так и при минимизации функции. Кроме этого, он легко распространяется на задачи многокритериальной оптимизации. Экспериментальные исследования показывают, что часто данный метод эффективней метода рулетки. N особей популяции P(k) 2 особи 54 2 особи 55 3.2.7. Метод Больцмана В этом случае при отборе особей используется подход, который используется в известном методе оптимизации «моделирование отжига», где при управлении процессом поиска применяется «искусственная температура». Для этого вводится действительная переменная T, которая, начиная с некоторого достаточно большого значения, постепенно уменьшается (по определенному закону) и изменяет вероятность отбора особей. Вероятность отбора особи, имеющей значение фитнесс-функции f(i), определяется следующим образом 1  e f ( ai ) / T  Ps (ai )   , (3.3) N  e f ( a ) / T  где e f ( a ) / T представляет среднее значение e f ( a ) / T по текущей популяции. Отметим, что с уменьшением температуры разность значений Ps (ai ) между худшими и лучшими особями увеличивается. Это позволяет на заключительном этапе сузить поиск в наиболее перспективной области пространства поиска, сохраняя при этом достаточную степень разнообразия в популяции. Показано, что для некоторых задач этот метод отбора дает лучшие результаты, чем стандартный пропорциональный отбор типа «рулетка»[3]. 3.2.8. Методы выбора пар для скрещивания До сих пор мы, в основном, рассматривали методы отбора родителей в промежуточную популяцию. Далее из этой популяции необходимо выбрать пары особей для выполнения операции скрещивания. Основными методами выбора пар особей являются следующие. Случайный выбор (панмиксия) родительской пары, при котором оба родителя случайным образом выбираются из всей промежуточной популяции. Следует отметить, что при этом любая особь может входить в 55 56 несколько пар. Этот метод является универсальным для решения различных задач, но достаточно критичен к численности популяции, поскольку его эффективность снижается с ростом мощности популяции N . Селективный выбор. Здесь родителями могут стать только те особи, значение целевой функции которых не меньше среднего значения по популяции при равной вероятности этих кандидатов составить брачную пару. Такой подход обеспечивает более быструю сходимость алгоритма, но неприемлем для мультимодальных задач (имеющих несколько экстремумов), для которых этот метод, как правило, быстро сходится к одному из решений. Это может привести к преждевременной сходимости к локальному экстремуму. Часто используется также два следующих подхода: инбридинг и аутбридинг. В них формирование пары происходит на основе близкого или дальнего родства соответственно. Под родством обычно понимается расстояние между особями популяции в пространстве параметров. В связи с этим различают генотипный и фенотипный инбридинг и аутбридинг. Инбридинг – здесь первый член пары выбирается случайно, а вторым является максимально близкая к нему особь. Аутбридинг формирует пары из максимально далеких особей. Комбинация этих походов используется при решении многоэкстремальных задач. 3.2.9. Неявные методы отбора, основанные на масштабировании фитнесс-функции Кроме рассмотренных выше явных методов отбора часто применяются также и неявные методы, которые, как правило, сводятся к масштабированию фитнесс-функции [1,4]. Масштабирование фитнесс-функции производится обычно в следующих случаях: 1) для предотвращения преждевременной сходимости ГА; 2) на последнем этапе выполнения ГА, когда в популяции сохраняется значительная неоднородность, однако среднее значение фитнесс-функции ненамного отличается от максимального значения. Масштабирование позволяет избежать ситуаций, в которых средние и лучшие особи дают практически одинаковое количество потомков, что считается нежелательным явлением. Преждевременная сходимость соответствует ситуации, когда в популяции доминируют лучшие, но еще не оптимальные особи. Это особенно характерно для ГА, использующих при отборе родителей метод рулетки. При этом часто возникают ситуации, когда через несколько поколений популяция состоит в основном из копий лучшей особи. Поскольку в качестве исходной популяции часто используется небольшая случайная выборка из пространства возможных решений, то маловероятно, что именно эта лучшая особь соответствует оптимальному решению. Масштабирование фитнесс-функции часто позволяет избежать доминирования неоптимальной особи, и, тем самым, предохраняет ГА от преждевременной сходимости. 56 57 Масштабирование выполняется с помощью трех основных преобразований фитнесс-функций: 1) линейное, 2) сигма-отсечение и 3) степенное. Линейное масштабирование сводится к линейному преобразованию фитнесс-функции следующего вида F=aF+b, где a и b- константы, которые обычно подбираются так, чтобы среднее значение фитнесс-функции после масштабирования было равно ее среднему значению до масштабирования, а максимальное значение фитнесс-функции после преобразования было кратным ее среднему значению. Здесь F и F соответствуют фитнесс-функции до и после преобразования. При этом коэффициент кратности обычно выбирается в пределах от 1,2 до 2 и необходимо следить, чтобы новая фитнесс-функция F не принимала отрицательных значений. Сигма отсечение основано на следующем преобразовании фитнессфункции (3.4) F  F  ( F  c   ) , где F означает среднее значение фитнесс-функции по популяции, с – малое натуральное число (обычно от 1 до 5), а  - стандартное отклонение по популяции. Если при этом значения F получаются отрицательными, то они полагаются равными нулю. При степенном масштабировании используется следующее преобразование F=Fk, где k – число, обычно близкое к 3. В общем случае к подбирается эвристическим путем с учетом специфики задачи. 3.3. Операторы рекомбинации (скрещивания, кроссинговера) Различают операторы двоичной и вещественной рекомбинации (скрещивания). Рассмотрим сначала более привычную (и уже знакомую нам), применяемую в простом ГА двоичную рекомбинацию. 3.3.1. Двоичная рекомбинация 3.3.1.1. Одноточечный кроссинговер Здесь случайным образом выбирается точка скрещивания с вероятностью Pc  0.5 и производится обмен фрагментами хромосом после точки скрещивания. Пример показан на рис.3.8. а: в: 0 1 1 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 57 58 а’: 0 1 1 1 0 0 1 0 1 в’: 1 0 0 1 1 1 0 1 0 Рис.3.8. Одноточечный кроссинговер 3.3.1.2. Многоточечный кроссинговер Разработаны различные обобщения классического одноточечного кроссинговера, которые наиболее полно представлены в [23]. При двухточечном кроссинговере потомки наследуют фрагменты хромосом родителей между двумя случайно выбранными точками скрещивания, как это, например, показано на рис. 3.9. Рис. 3.9. Пример двухточечного кроссинговера Графически это пример удобно представить в виде, показанном на рис.3.10. Многоточечный кроссинговер является обобщением предыдущих операторов на случай большего числа точек скрещивания. Например, трехточечный кроссинговер представлен на рис.3.11. Многоточечный кроссинговер с большим четным количеством точек скрещивания графически удобно представить для хромосом в виде «колец», что показано на рис.3.12 [1,4]. При этом хромосома рассматривается как замкнутое кольцо, а точки скрещивания выбираются с равной вероятностью по всей его окружности. Например, на рис.3.10 обмен производится фрагментами между 4-й и 6-й точек скрещивания родительских особей, что также иллюстрируется на рис.3.11. 58 59 Рис. 3.10. Пример двухточечного кроссинговера Рис.3.11. Пример трехточечного кроссинговера Рис.3.12. Пример четырехточечного кроссинговера Кроссинговер с нечетным количеством точек скрещивания можно представить таким же способом, если добавить дополнительную точку скрещивания в нулевой позиции. 3.3.1.3. Однородный кроссинговер Этот вид скрещивания радикально отличается от предыдущих видов. Здесь каждый ген потомка создается путем копирования соответствующего гена из первого или второго родителя, то есть каждая позиция потенциально является точкой кроссинговера. Для этого случайным образом генерируется двоичная маска кроссинговера той же длины (с тем же числом бит), что у хромосом родителей. Четность бита маски показывает родителя, из которого копируется ген потомка. Для определенности допустим, что 1 соответствует первому родителю, а 0 – второму. На рис.3.13 показана схема выполнения этого типа кроссинговера на конкретном примере. Каждый бит потомка 59 60 копируется из 1-го или 2-го родителя в соответствии со значением этого бита маски. 1 0 0 1 0 1 1 1 0 0 Маска ОК 1-й родитель 1 0 1 0 0 0 1 1 1 0 Потомок 1 1 0 0 0 0 1 1 1 1 2-й родитель 0 1 0 1 0 1 0 0 1 1 Рис.3.13. Однородный кроссинговер Таким образом, потомок содержит смесь генов из каждого родителя. 3.3.1.4. Ограниченный кроссинговер В этом виде скрещивания точки кроссинговера могут выбираться только там, где значения генов у родителей различны. 3.3.2. Рекомбинация действительных значений При этом хромосома представляется (вещественными) числами. действительными 3.3.2.1. Дискретная рекомбинация Этот вид скрещивания определен над векторами, компонентами которых являются вещественные числа. Рассмотрим это на примере двух особей, соответствующие вектора которых имеют три целых значения. Для каждой переменной (позиции) значение переменной выбирается из первого или второго родителя с равной вероятностью. Пример выполнения этого оператора показан на рис.3.14. Здесь образцы (маски) показывают принадлежность данной компоненты потомка определенному родителю. Отметим, что этот тип рекомбинации применим к значениям любого типа. 3.3.2.2. Промежуточная рекомбинация Этот метод применим только для особей, представленных только вещественными значениями. Здесь значения потомков строятся в окрестности или между значениями родителей. В случае промежуточной рекомбинации потомки O1 и O2 формируется следующим образом: O1  P1  1  P2  P1  O2  P1   2  P2  P1  , , (3.5) 60 61 1-й родитель 2-й родитель 1-й образец (маска) 2-й образец (маска) 1-й потомок 2-й потомок 12 25 5 123 4 34 2 2 1 1 2 1 123 4 5 12 4 5 Рис.3.14. Дискретная рекомбинация где P1 , P2 – вещественные значения, представляющие первого и второго родителя; Oi– вещественное значение, представляющее потомка;  i - масштабирующий множитель, который выбирается случайным образом из отрезка [-d, 1+d]. При обычной промежуточной рекомбинации d  0 и  i  0,1. Для обобщенной промежуточной рекомбинации d  0 , обычно полагают d  0,25 . Значение каждой переменной, в том числе и для векторов, формируется по приведенному выражению. Отметим, что здесь используются чисто арифметические операции (сложение и умножение). Заметим, что при d=0 потомки принадлежат отрезку [ P1 , P2 ] . Эти операторы совершенно не похожи на классический кроссинговер. Фактически, этот оператор заимствован из другого направления эволюционных вычислений «эволюционных стратегий». На рис.3.15 показан пример выполнения этого оператора для тех же данных, которые использовались в предыдущем примере. 1-й родитель 12 25 5 2-й родитель 123 4 34 Случайно выбраны следующие значения коэффициента  0,5 1,1 0,1 1-й образец 1 0,1 0,8 0,5 2-й образец 2 1-й потомок 67,5 1,9 7,9 2-й потомок 23,1 8,2 19,5 Рис.3.15. Промежуточная рекомбинация 61 62 Для примера подробно приведем выполнение оператора для 1-ой компоненты O1  P1  1  P2  P1   12  0.5  123  12  67.5 . (3.6) 3.3.2.3 Линейная рекомбинация Этот вид оператора аналогичен предыдущему, за исключением того, что значение масштабирующего множителя  одинаково для всех переменных (компонент) векторов. Пример выполнения этого оператора представлен на рис.3.16. 1-й родитель 12 25 5 2-й родитель 123 4 34 Случайно отобраны следующие значения коэффициента  1-й образец  = 0,5 2-й образец  = 0,1 1-й потомок 67,5 14,5 19,5 2-й потомок 23,1 22,9 7,9 Рис.3.16. Линейная рекомбинация 3.3 Оператор мутации После выполнения операторов рекомбинации (скрещивания) полученные потомки с вероятностью Pm подвергаются мутации, которая может быть выполнена различными способами. 3.3.1 Двоичная мутация 3.3.1.1 Классическая мутация Этот вид оператора уже рассматривался в простом ГА. Здесь для каждой особи случайно выбирается позиция и с малой вероятностью (от Рm=0,01 до Рm=0,001) выполняется инвертирование значения переменной в выбранной позиции. Пример выполнения этого оператора представлен на рис.3.17. 0 1 1 1 0 0 1 1 0 1 0 0 1 1 0 0 0 1 1 0 1 0 Рис.3.17. Классическая мутация 3.3.1.2 Оператор инверсии 62 63 Иногда используется следующий оператор инверсии, фактически являющийся разновидностью мутации. При этом случайным образом выбираются две позиции в особи и далее производится обмен значениями генов между ними. Пример выполнения этого оператора представлен на рис.3.18. 0 1 1 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1 0 Рис.3.18.Инверсия 3.4 Мутация над вещественными числами Мутация над вещественными потомками выполняется путем сложения особи с небольшим случайным значением, которое называется шагом мутации. Выбор размера шага мутации зависит от рассматриваемой проблемы, и шаг в общем случае может изменяться в процессе решения задачи. Маленький шаг дает большую точность, но ведет к большим временным затратам. Мутация с постоянным шагом и постоянной вероятностью называется однородной. Оператор мутации над вещественным числом выполняется следующим образом Vm  V  r   , (3.7) где V, Vm – значения вещественной переменной до и после мутации; r=0.5 (диапазон изменения переменной) и ∆ - случайное число от 0 до 1. Часто для повышения эффективности поиска вероятность мутации и шаг изменяются в процессе решения задачи. Рассмотрим далее способы изменения вероятности мутации. Мутация с равной вероятностью может привести как к увеличению, так и к уменьшению значения целевой функции. На этапе сходимости ГА к оптимуму целесообразно уменьшать вероятность случайной мутации. Обычно на начальном этапе Pm  0.050.1 , а на конечном этапе вероятность мутации уменьшают. Для реализации этой процедуры иногда используют метод моделирования отжига (simulation annealing), который дает следующий закон изменения вероятности мутации: 1 P  P0  e t , m m  (3.8) где t – номер поколения. Здесь изменяется шаг мутации. Вначале шаг мутации имеет достаточно большое значение, которое далее постепенно уменьшается. Рассмотрим этот тип оператора для векторного случая 63 64 Svt  V1 ,V2 ,,Vk ,Vm Vk  lk ,U k  . В результате выполнения мутации получаем следующий вектор (особь популяции) Svt 1  V1 ,V2 ,,Vk' ,Vm k  1, n , (3.9) где компонента вектора вычисляется следуюшим образом V  (t ,U  V ) при случ . число  0 k k  k , (3.10) V 'k   Vk  (t ,Vk  lk ) при случ . число  1  t , y   0, y  и t, y  определяет шаг мутации, который с увеличением где номера поколения t уменьшается:  (t , y )  0 t  . Один из вариантов реализации функции, определяющей шаг ∆(t,y), следующий:  t   1  b   (t , y )  y  1  r  T   , (3.11)   где r  1,n (r-случайное число) и T – максимальное число поколений; b  2 – параметр, определяющий степень неоднородности. На рис.3.19 показан для наглядности график изменения шага мутации, который в пределе стремится к 0. Рис.3.19. Уменьшение шага мутации 3.5. Сокращение промежуточной популяции Необходимой компонентой является устранение плохих решений, полученных в процессе формирования новой популяции. 64 65 3.5.1. Глобальная редукция Промежуточную популяцию (репродукционную группу) составляют все особи t -го поколения и новые особи, полученные в результате скрещивания и мутации. Численность этой популяции можно определить следующим образом Rt 1  r t  rcrt  rmt , (3.12) где: r t - число особей предыдущей популяции; rcrt – численность особей, полученных путем скрещивания; rmt – число «мутантов». Обычно в стационарных ГА мощность популяции поддерживается постоянной N  Pt  . Поскольку R t 1  N , то необходимо устранить неудачные решения. Для этого существуют различные методы редукции. 3.5.1.1. Чистая замена В простейшем случае с помощью скрещивания и мутации генерируются столько потомков, сколько было родителей. Далее родители устраняются, а потомки формируют следующее поколение Pt  1 . При этом каждая особь живет лишь одно поколение. Такая схема часто используется в простом ГА. Однако при этом очевидно не исключено, что некоторые очень хорошие решения могут быть заменены худшими, и лучшее решение будет потеряно. 3.5.1.2. Элитарная схема В ней потомков генерируется меньше, чем было родителей. Далее вновь построенные потомки заменяют худших родителей согласно значениям фитнесс-функции. Для этой схемы возможна преждевременная сходимость к локальным экстремумам. 3.5.1.3. Равномерная случайная замена При таком подходе потомков также генерируется меньше, чем было родителей, далее случайным образом удаляется необходимое число родителей, которые заменяются новыми потомками. 3.5.1.4. Пропорциональная редукция Здесь потомков генерируется больше, чем необходимо для замены. Далее заменяют заданное число родителей только лучшими потомками согласно значениям фитнесс-функции. 3.5.1.5. Селекционная схема Здесь родители и потомки выступают на равных правах - они помещаются в одну репродукционную группу. В ней все особи этой группы 65 66 ранжируются и в следующее поколение включаются только лучшие N особей. Иногда применяется следующая модификация этого метода. Сначала вычисляется среднее значение ЦФ группы и в следующее поколение включаются те особи, у которых значение ЦФ больше среднего значения группы. В общем случае к репродукционной группе R t 1 может быть применен любой метод отбора родителей, которые были рассмотрены в разделе 3.2. 3.5.2. Локальная замена При локальном отборе особи выбираются из ограниченного окружения множества соседей. Замена особей потомками выполняется по такой же схеме. Таким образом сохраняется локальность информации. При этом используются те же структуры и отношения соседства, что и в разделе 3.2.4. Родитель особи определяются первым родителем из локального окружения (множества соседей). Для выбора удаляемых родителей и отбора потомков для замены применяются следующие схемы:  Ввести в новое поколение каждого потомка и заменить случайным образом особи из их окружения;  Ввести каждого потомка и заменить худшей особью соответственного окружения;  Ввести потомка лучше, чем худшая особь в окружении, и заменить худшие особи. 3.6. Асинхронные генетические алгоритмы До сих пор мы рассматривали стационарные синхронные эволюционные алгоритмы, где мощность популяции поддерживается постоянной и переход к следующему поколению «синхронизирован». Здесь обрабатываются все потомки предыдущего поколения, а затем следует переход на следующую итерацию (поколение). Иногда на практике применяется и асинхронный эволюционный алгоритм, где нет явного разбиения эволюции на поколения, а процесс развития реализуется «по событию» в виде непрерывного потока событий отбора, кроссинговера, мутации и т.п. Здесь вновь порожденные потомки сразу замещают (в некотором смысле худшие) особи (не дожидаясь остальных родительских пар своего поколения). Ниже представлен один из возможных вариантов асинхронного алгоритма реализации ГА с применением турнирного отбора родителей. 0) установка параметров эволюции; 1) инициализация начальной популяции; 66 67 2) случайный выбор подмножества особей популяции – участников турнира; 3) оценка фитнесс-значений каждого участника турнира; 4) отбор победителей турнира; 5) выполнение генетических операторов кроссинговера и мутации для победителей; 6) замена проигравших особей потомками победителей; 7) если критерий окончания не выполнен, то переход к п.2; 8) выбор лучшего решения в конечной популяции. Следует отметить, что такой метод, как правило, проще в реализации (особенно аппаратной) и имеет некоторые преимущества. 3.7. Генетические микроалгоритмы Данная модификация предназначена для решения задач, которые не требуют популяций с большим числом особей и длинных хромосом. Такой подход оправдан в том случае, когда решение (не обязательно глобальный оптимум) необходимо найти как можно быстрее. В этом случае необходимо уменьшить трудоемкость, связанную с большим количеством итераций, ценой возможно ухудшения качества решения. Такой подход, например, реализован в программе FlexTool [4] следующим генетическим микроалгоритмом. 1. Формирование популяции из 5 особей. При этом можно либо случайным образом выбирать все 5 хромосом, либо сохранять одну «хорошую» особь, полученную на предыдущих итерациях, и случайным образом генерировать остальные 4 особи. 2. Расчет значений фитнесс-функции особей в популяции и выбор лучшей особи. Присвоить ей номер 5 и перенести в следующее поколение (согласно элитарной стратегии). 3. Выбор для репродукции остальных четырех хромосом на основе турнирного метода селекции. При этом хромосомы группируются случайным образом, и соседние пары соперничают за оставшиеся 4 места. Необходимо следить, чтобы родительская пара не формировалась из двух копий одной и той же хромосомы. 4. Выполнение кроссинговера с вероятностью pc=1 (вероятность мутации положить pm=0). 5. Проверка сходимости алгоритма (на основе сравнения фенотипов или генотипов). Если условие останова не выполнено, то переход на шаг 2, иначе конец. Отметим, что в генетическом микроалгоритме используется небольшой фиксированный размер популяции и элитарная стратегия отбора родителей, которая предотвращает потерю хороших особей. Мутация здесь не применяется поскольку разнообразие генетического материала обеспечивается формированием новой популяции при каждом рестарте 67 68 алгоритма( переходе на шаг 1 при обнаружении сходимости). Процедуры «старта» и «рестарта» предназначены для предотвращения преждевременной сходимости. 3.8. Генетические алгоритмы с изменяемой мощностью популяции Мощность популяции N является важнейшим параметром ГА, который критичен во многих приложениях. Если N мало, то ГА работает быстро, но при этом увеличивается опасность преждевременной сходимости к локальному экстремуму. Большая мощность популяции увеличивает генофонд, но процесс поиска замедляется. На разных этапах работы ГА оптимальное значение N может быть различным. На начальном этапе N должно быть большим, а на заключительном N можно уменьшить. При одном из подходов в ГА с изменяемым размером популяции каждой особи после ее рождения на текущем этапе оценки целевой функции (ЦФ) присваивается «время жизни» (life time) L f – параметр, зависящий от ЦФ особи. Таким образом, каждая особь живет определенное число поколений и умирает по окончании срока жизни. Очевидно, значение этого параметра влияет на размер популяции. В этом случае ГА можно реализовать, например, следующим образом [5]. Нестационарный_ГА { t =0; Инициализация; Оценка ЦФ p(t); While (условие окончания не выполнено) { t=t+1; Увеличение возраста каждой особи на 1; Рекомбинация p(t): Мутация p(t): Оценка ЦФ p(t): Определение срока жизни особей; Удаление из p(t) всех особей с возрастом больше жизни; } } В срока Здесь в текущем поколении t алгоритм обрабатывает популяцию Pt  . процессе рекомбинации и мутации генерируется промежуточная 68 69 популяция, состоящая из потомков, и ее размер пропорционален числу t t t исходной rcr  rm  ra  r  P . Тогда Pt 1  Pt   ra  Dt  – число особей в новой популяции. Срок жизни для каждой особи определяется после оценки ЦФ (по формулам, приведенным ниже) и является окончательным, то есть постоянным в процессе эволюции. В таком случае особь живет определенное число поколений, а затем умирает. Срок жизни определяет число поколений, в течении которых особь держится в популяции. Очевидно, что в этом случае, чем больше срок жизни, тем больше потомков может дать особь, так как на каждом этапе родители для рекомбинации выбираются случайно с равной вероятностью. При этом подходе важнейшую роль играет метод определения срока жизни особи. Очевидно, постоянное значение L f  2 для каждой особи ведет к экспоненциальному росту размеров популяции. Поэтому для каждой особи срок жизни вычисляется индивидуально в зависимости от значения ее ЦФ. Наиболее часто используются следующие три способа определения срока жизни. Для их определения введем следующие обозначения: t f - среднее значение ЦФ по популяции; f max - максимальное значение ЦФ по популяции; f min - минимальное значение ЦФ по популяции; f a max - абсолютное максимальное значение; f a min - абсолютное минимальное значение; Lmax - максимальный срок жизни; Lmin - минимальный срок жизни. 1. При пропорциональном методе определения срока жизни L f определяется по следующей формуле:   f i  L f  min Lmin    , Lmax  , f   1    Lmax  Lmin  (используется для всех формул). где 2 2. При линейном методе определения срока жизни L f  Lmin  2    3. (3.13) f i   f a min f a max  f a min В билинейном методе определения срока жизни 69 (3.14) 70  f i   f min Lmin    , если f  f i   f  f min   Lf   (3.15) 1 f i   f , если f  f i    Lmin  Lmax     2  f max  f  Очевидно, что первый метод соответствует пропорциональному отбору отбора родителей - «рулетке». К минимальному сроку жизни добавляется премиальный срок, который пропорционален значению ЦФ для данной особи. Однако эта стратегия имеет серьезный недостаток – она не учитывает информацию о некоторых объективных характеристиках особи, такой, например, как отношение f i  f i  (или ) целевой функции по популяции. f max f min Эту проблему решает вторая (линейная) стратегия, где срок жизни определяется исходя из значения ЦФ данной особи относительно максимального значения в популяции f max . Но этот метод тоже имеет свои недостатки - если в популяции много особей имеют значение ЦФ стремящееся к максимальному ( f i   f max ) значению, то такой подход приведет к чрезмерному увеличению размера популяции. В третьей стратегии (билинейной) предпринята попытка найти компромисс между первыми двумя методами. В ней учитываются разница между сроками жизни, близкими к лучшей особи, используя информацию о среднем значении популяции. Однако в тоже время принимается во внимание минимальное и максимальное значение по популяции. 3.9. Гибридные генетические алгоритмы Одним из важнейших преимуществ ГА является то, что они прекрасно сочетаются с другими методами оптимизации, поэтому разработано множество гибридных ГА. Пожалуй самым распространенным подходом является включение локальной оптимизации наряду с генетическими операторами в классическую блок-схему простого ГА. В этом случае локальная оптимизация применяется к каждому полученному потомку, чтобы «сдвинуть» его в сторону локального оптимума перед внедрением его в новую популяцию. При этом ГА используется для глобального расширения пространства поиска, в то время как эвристические методы применяются для «эксплуатации» ближайшего окружения особей. Вследствие того, что ГА и эвристические методы имеют взаимно дополняющие свойства, гибридные ГА часто превосходят по характеристикам входящие в него компоненты. Другой распространенной формой гибридизации является внедрение адаптации параметров ГА. Характеристики ГА характеризуются балансом между расширением и эксплуатацией пространства поиска решений, который 70 71 в значительной степени определяется значениями основных параметров ГА, таких как мощность популяции, максимальное число поколений, вероятностей кроссинговера и мутации. Выбор значений этих параметров является одной из важнейших задач при разработке ГА. Комбинирование ГА и эвристик локального поиска исследовалось многими авторами и предложено множество методов гибридизации, но наиболее распространенными является два: 1) эволюция Ламарка; 2) Балдвин- эффект [9]. Оба подхода используют то, что особь обучается в течение времени своего существования. В случае эволюции Ламарка результирующая особь (после применения локального поиска) помещается назад в популяцию, как показано на рис.3.20. При втором подходе изменяется только значение фитнесс-функции особи, а генотип остается неизменным. Отметим, что классический ГА разработан Холландом на основе моделирования эволюции Дарвина. Но еще в XIX веке в теорию Дарвина были предложены Ламарком дополнения, где изменения особи в течение ее жизни вследствие воздействия окружающей среды передавались потомкам. Эта теория позволяет организмам накопленный опыт и знания в течение жизни передавать потомкам. Далеко не все биологи разделяют эту точку зрения, но этот эффект имеет место, например, в эволюции общества. Использование эволюции Ламарка позволяет сфокусировать поиск на более перспективных областях. В этом случае особь после обучения (методом эвристики локального поиска) помещается назад в текущую популяцию и имеет шанс на этапе отбора и кроссинговера передать информацию потомкам. 71 72 Потомок C(t) Популяция P(t) 1100101010 1011101110 кроссовер 1100101010 CC(t) 1011101110 . . . 1100101110 1011101110 0011011001 1100110001 мутация CM(t) 1100101110 t←t+1 1011101110 Отбор P(t)+C(t)+ Cλ(t) Рулетка оценка Вычисление фитнессфункции особей Поиск экстре мума Cλ(t) 000100001 декодер декодер Рис.3.20 Общая структура гибридного ГА. Эксперименты на некоторых тестовых задачах показали [8], что стратегия с Балдвин-эффектом чаще сходится к глобальному оптимуму, в то время как эволюция Ламарка склонна к сходимости к локальному оптимуму с использованием одной и той же эвристики локального поиска. Однако, во всех экспериментах стратегия Балдвина имеет меньшую скорость сходимости, чем эволюция Ламарка. В ранних работах первого направления в ГА использовались операторы Ламарка [9]. Некоторые авторы [10] ввели вероятность Ламарка для мутации с тем, чтобы получить более контролируемый оператор мутации и операторы локального поиска. Пусть P(t) и C(t) обозначают множество родителей и потомков текущей популяции t. Ниже представлен в виде псевдокода укрупненный алгоритм эволюции Ламарка. procedure: гибридный ГА 72 73 input: обрабатываемые данные, параметры ГА ouput: лучшее решение begin: t←0; инициализация начальной популяции P(t); оценка особей популяции P(t); while(не выполнено условие останова) do генерация потомков C(t) из P(t) посредством кроссинговера; генерация потомков C(t) из P(t) посредством мутации; локальный поиск экстремумов C(t); оценка особей популяции P(t); отбор следующей популяции C(t+1) из C(t) и P(t); t←t+1; end ouput лучшее решение end Эти идеи получили развитие в меметических алгоритмах [11,12], в которых локальный поиск также играет важнейшую роль. Термин мем (meme) заимствован из теории Докинза [13] и означает единицу воспроизводимой информации при обмене информацией между людьми. Здесь ключевое различие лежит между генами и мемами. Перед тем, как мем передается, он обычно адаптируется передающим лицом так как оно думает, понимает и преобразует мем, в то время как ген передается без изменения целиком. В [14] дано формальное описание меметического алгоритма, которое позволяет с единой точки зрения рассматривать генетический и меметический алгоритм. Следуя [14], если в ГА вводится локальный оптимизатор, который применяется для каждого потомка перед внедрением его в популяцию, то меметический алгоритм можно рассматривать как специальный вид гибридного ГА с локальным поиском. Рекомбинация и мутация обычно дают решения, которые выходят за зону локального оптимума, но локальный оптимизатор может вернуть их в эту зону и таким образом потомок помещается в окрестность оптимума, как показано на примере рис.3.21. Поскольку ГА навеяны идеей эволюции, естественно ввести элементы адаптации не только в процесс поиска решений задачи, но и в настройку значений параметров ГА для данной проблемы. 73 74 Рис.3.21. Пример применения локального поиска в ГА В последние годы проведено достаточно много исследований в этом направлении, когда в основном рассматриваются два вида адаптации: 1) Адаптация к проблеме; 2) Адаптация к процессу эволюции. Разница между ними в том, что первая модифицирует некоторые компоненты ГА, такие как вид представления особи, кроссинговер, мутация и отбор. Естесственно, для удачного выбора или модификации компонентов необходимо понимать суть решаемой задачи. Во втором виде адаптации предлагается способ настройки значений параметров и конфигурации ГА в процессе решения задачи. Следуя [15, 16] последний вид адаптации можно разбить на следующие классы: - адаптация параметров установки; - адаптация генетических операторов; - адаптация отбора; - адаптация представления решения; - адаптация фитнесс-функции. Из этих видов в последние десять лет исследовались различные способы адаптации параметров, таких как вероятности кроссинговера и мутации, мощность популяции, которые играют решающую роль в балансе расширения и эксплуатации пространства поиска решений. Ключевым вопросом является выбор значений параметров для эффективного решения данной проблемы. Обычно в простом ГА используются фиксированные значения параметров, которые находятся методом проб и ошибок. Поскольку сам ГА является динамическим и адаптивным процессом, то фиксированные значения параметров противоречат самому духу эволюции. Поэтому возникла естественная идея попробовать изменять значения параметров в процессе поиска решения. Это можно сделать различными способами: - применять некоторые правила; - использовать обратную связь в виде информации о текущем состоянии поиска; - внедрить некоторый механизм самоадаптации. 74 75 В работах [15,17] представлен обзор используемых на текущий момент методов адаптации в ГА, в котором выделены три основные категории. 1) Детерминированная адаптация, где значение параметра изменяется по некоторому детерминированному правилу. Например, вероятность мутации уменьшается в соответствии со следующей формулой: Pm  0.5  0.3 t , где t – номер текущего поколения (итерации) и maxGen – max Gen максимально допустимое число поколений. Согласно этому правилу вероятность мутации уменьшается от 0.5 до 0.3 при росте номера поколения эволюции. 2) Адаптивная адаптация, которая имеет место при наличии некоторой формы обратной связи с процессом эволюции и используется для определения направления изменения параметра. Одним из первых примеров является “правило успеха 1/5” Решенберга в эволюционных стратегиях (см. раздел 9.1) для определения коррекции шага мутации. Правило гласит, что если доля успешных мутаций (дающих улучшение решения) больше 1/5, то шаг мутации можно увеличить, в противном случае этот шаг следует уменьшить. Известны примеры адаптивных фитнесс-функций [18], адаптивного механизма поиска соотношения между значениями вероятностей кроссинговера и мутации [19] и т.п. 3) Самоадаптация, где значения параметров также эволюционируют в процессе поиска решений. При этом значения параметров кодируются и включаются в хромосомы особей, но не учитываются при вычислении значений фитнесс-функции. 3.10.1. Адаптация мощности популяции Отметим, что изменение мощности популяции между двумя соседними поколениями прежде всего влияет на функционирование оператора отбора. Пусть nt и nt+1 обозначают мощность популяции текущего и последующего поколения соответственно. Отбор особей можно рассматривать как повторяющийся процесс nt+1 операторов отбора с вероятностью pj для j-ой особи. Для большинства методов отбора, таких, как например, пропорциональный или турнирный отбор с замещением, вероятность выбора pj остается неизменной при выполнении nt+1 операторов. Тогда ожидаемое количество копий j-ой особи можно выразить как c j, t  1  p j nt 1c j, t  , где c(j,t) – число копий j-ой особи в поколении t. Ожидаемое количество копий j-ой особи прямо пропорционально мощности популяции следующего поколения. Таким образом, долю в популяции особей, связанных с j-ой особью после отбора можно выразить следующим выражением: c j, t  1  c j, t  1 p j nt 1c j, t    p j c j , t  , nt 1 nt 1 которое не зависит от размера следующей популяции на том основании, что изменение мощности популяции несущественно влияет на значение 75 76 вероятности pj . Отметим, что ГА, где мощность популяции уменьшается с ростом поколения, имеет большую начальную и меньшую конечную популяцию. Это повышает эффективность ГА, поскольку большая начальная популяция покрывает большее подпространство поиска, а в конце процесса, когда найдена «зона интереса», для сходимости к оптимуму достаточно и небольшого количества особей в популяции. Основываясь на этих предположениях, был предложен так называемый пилообразный ГА [20], где изменение мощности популяции комбинируется с реинициализацией, которая выполняется для улучшения характеристик ГА. При этом среднее значение мощности популяции по периоду n соответствует постоянной популяции ГА с той же вычислительной сложностью. Кроме этого, закон изменения мощности популяции характеризуется амплитудой D и периодом T. В этой нотации размер популяции изменяется следующим образом:  2D   t  1     t  T  int  nt   int  n  D    1 T 1  T    .  На рис.3.22 представлен пример пилообразного изменения мощности популяции. вн едрен ие средний случайн ых _ особей размер _ n(t ) популяции поколение t Рис.3.22 Пилообразное изменение количества особей в популяции. 3.10.2. Адаптация вероятностей кроссинговера и мутации В адаптивных генетических алгоритмах изменяются параметры ГА, прежде всего, вероятности кроссинговера и мутации Pc и Pm . Для оптимизации, особенно мультимодальных функций, наиболее существенными являются две характеристики ГА: - способность сходиться к оптимуму (локальному или глобальному) после нахождения области, содержащей этот оптимум; - способность находить новые области в пространстве решений в поисках глобального оптимума. 76 77 Баланс между этими характеристиками ГА определяется значениями и Pm и типом используемых генетических операторов вероятности Pc и Pm ведет к (прежде всего кроссинговера). Увеличение значений Pc расширению пространства поиска. Обычно используют следующие значения вероятностей - Pc  0.5;1 и Pm  0.001;0.01 . Далее мы рассмотрим другой подход [7], который и Pm в зависимости от значения использует различные значения Pc ЦФ текущих особей. Для мультимодальных функций существует серьезная проблема преждевременной сходимости к локальным экстремумам. и Pm адаптивно, с целью предотвращения Чтобы изменять Pc преждевременной сходимости к локальному экстремуму, надо научиться идентифицировать ситуации, когда ГА сходится к оптимуму. Рассмотрим этот подход на примере поиска максимума для мультимодальной функции (которая имеет несколько экстремумов), которая показана на рис. 3.23. f(x) x Рис.3.23. Мультимодальная функция Один из возможных способов обнаружения сходимости – наблюдение разности среднего и максимального значения целевой функции по популяции ( f max  f ) . Обычно эта разность меньше для популяции, которая сходится к оптимуму, чем для популяции, «разбросанной» по пространству поиска решений. Будем использовать разность ( f max  f ) в качестве основного признака сходимости к оптимуму, причем не обязательно глобальному. и Pm должны увеличиваться при Поскольку вероятности Pc преждевременной сходимости к локальному оптимуму (чтобы «выпрыгнуть из ловушки» локального экстремума), то значение изменяться обратно пропорционально разности ( f max Pc  k1 f max  f Pm  77 k2 f max  f . ( f max  f )  f ): должны (3.25) 78 и Pm не зависят от значений ЦФ для конкретной особи, Здесь Pc а определяются для всей популяции, но для разных популяций различных поколений они уже будут разными. Отметим, что как для хороших решений с высокими значениями целевой функции, так и для плохих, используются одни и те же величины Pc и Pm . Это не рационально, так как когда популяция сходится к и Pm увеличиваются, глобальному или локальному оптимуму, то Pc что ведет к разрушению близких к оптимуму решений. В результате популяция может не сойтись к глобальному оптимуму. Таким образом, мы избежали ловушки локального экстремума ценой снижения характеристик ГА по поиску глобальных экстремумов. Чтобы решить эту проблему, нужно сохранить хорошие решения текущей популяции. Это можно сделать, полагая низкие значения и Pm для особей с высоким значением ЦФ и высокие вероятности Pc и Pm для плохих особей с низкими значениями ЦФ. Тогда значения Pc лучшие решения будут способствовать сходимости, а худшие – предотвращать ГА от «ловушек» локальных экстремумов. Таким образом, и Pm должны зависеть не только от разности значение Pc ( f max  f ) , но еще и от значений ЦФ конкретных особей. Чем ближе значение функции к максимальному, тем меньше должно быть значение Pc и Pm : Pc  k1  Pm  k 2  f max  f ' k1  1 , f max  f f max  f f max  f k2  1 , , (3.26) где f  – лучшее значение целевой функции у двух родителей. Положим Pc  Pm  0 для решений, имеющих максимальное значение ЦФ и Pc  k1 , f, f Pm  k 2 , f, f . (3.27) , Отметим, что для плохих решений ( f , f  f ) значения вероятностей Pc и Pm в соответствии с формулой (3.27) могут быть больше 1, что некорректно. Поэтому для плохих решений примем: Pc  k 3 , f, f Pm  k 4 , f, f 78 79 В итоге получим:  f max  f , , k 1  Pc   f max  f k , иначе  3 f, f f max  f  , k 2  Pm   f max  f k , иначе  4 k1  k 3  1 k 2  k 4  0.5 f  f , (3.28) . Лучшие решения при этом сохраняются и переходят в следующее поколение. Этот факт может привести к чрезмерному росту популяции, что чревато преждевременной сходимостью. Поэтому иногда дополнительно вводится одна (default) мутация (с вероятностью Pd  0.005 ) для всех особей популяции. Существуют и более строгие адаптивные ГА, где вероятности Pc и Pm вычисляются аналитически, но они, как правило, сильно привязаны к конкретным задачам. Достаточно эффективным средством адаптации является использование «нечетких контроллеров» в виде, например, системы продукций в нечеткой логике. Ключевые термины: Модификации генетических алгоритмов, отбор родителей, оператор кроссинговера, оператор рекомбинации, оператор мутации, стационарный генетический алгоритм, динамический генетический алгоритм, генетический микроалгоритм, адаптивный генетический алгоритм, ниши, меметический генетический алгоритм, эволюция Ламарка, нечеткий контроллер. Контрольные вопросы 1. Какие методы применяются для генерации начальной популяции? 2. Какая информация используется при отборе родителей? 3. Какие недостатки имеет «метод рулетки»? 4. Чем отличается ранжирование от пропорционального отбора? 5. Что такое локальный отбор? 6. Опишите метод турнирного отбора. 7. Как используется метод Больцмана при отборе особей? 8. Опишите методы отбора пар для скрещивания. 9. Что такое неявные методы отбора? 10. Опишите двоичную рекомбинацию. 11.Чем отличается многоточечный кроссинговер от классического? 12. Что такое однородный кроссинговер? 79 80 13.Чем отличается рекомбинация действительных чисел от классического кроссинговера? 14. Что такое дискретная рекомбинация? 15. Опишите промежуточную рекомбинацию. 16. Чем отличается линейная рекомбинация от промежуточной? 17. Что такое инверсия? 18. Как выполняется мутация над вещественными числами? 19. Чем отличается неоднородная мутация от обычной? 20. Какие существуют методы сокращения популяции? 21.В каких случаях целесообразно применять генетический микроалгоритм? 22. Опишите нестационарный ГА. 23.Чем заменяется отбор родителей в нестационарном ГА? 24. Какие методы определения сроков жизни вы знаете? 25.Что такое ниши в ГА? 26.Чем эволюция Ламарка отличается от эволюции Дарвина? 27.Опишите гибридный ГА на основе эволюции Ламарка. 28. В чем заключается адаптация в ГА? 29. Как изменяются вероятности кроссинговера и мутации при адаптации? 30.Какие виды адаптации ГА вы знаете? 31. Как можно выполнить адаптацию числа особей популяции? 32. Как можно выполнить адаптацию значений вероятностей кроссинговера и мутации. 33.Опишите адаптивный ГА на основе нечетких контроллеров. Краткие итоги:  рассмотрены различные модификации и обобщения ГА;  описаны различные виды отбора родительских особей;  показаны разные виды кодирования потенциальных решений;  представлено множество генетических операторов кроссинговера и мутации;  рассмотрены динамические ГА, где в процессе поиска изменяется мощность популяции;  писаны меметические ГА;  рассмотрены гибридные ГА;  представлены ГА на основе моделирования эволюции Ламарка;  описаны различные виды адаптивных ГА, где при поиске решений изменяются параметры ГА Список литературы 1. Скобцов Ю.А., Скобцов В.Ю. Современные модификации и обобщения генетических алгоритмов // Таврический вестник компьютерных наук и математики.Симферополь: 2004, №1. – с.60-71. 80 81 Скобцов Ю.А. Основы эволюционных вычислений.- Донецк: ДонНТУ, 2008.- 326с. 3. Mitchel М. An introduction to genetic algorithms.The MIT Press, Cambridge, Massachusetts.-1998.-210 p. 4. Рутковская Д., Пилинский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы. -М:Горячая линия, 2004.452с. 5. Michalevich Z. Genetic Algorithms + data structures=Evolution Programs. Springer.-1999. 6. Patnaik L. M., Mandavilli S. Adaptation in genetic algorithms. In: Genetic algorithms for pattern recognition.-CRC Press.-1996.-P.45-64. 7. Mahfoud S.W. A comparison of parallel and sequential niching methods.//Proceedings of VI International conference on genetic algorithms.1995.-P.136-143. 8. Whitley D., Gordon V., Mathias K. Lamarkian evolution, the Baldwin effect & function optimization, in Davidor Y., Schwefel H., Manner R., editors, Parallel problem solving from nature: PPSN III, Berlin, Springer-Verlag: 1994.- P.6-15. 9. Grefenstette J.J.Lamarkian learning in multi-agent environment//Proceedings of the 4th international conference on genetic algorithms, San Francisko, Morgan Kaufman Publishers:1991. 10. Davidor Y.A genetic algorithm applied to robot trajectory generation. Davis L.editor, Handbook of genetic algorithms: New York, Van Nostrand Reinhold, 1991. 11. Moscato P., Norman M. A memetic approach for the traveling salesman problem: implementation of computational ecology for combinatorial optimization on message-passing systems//Proceedings of international conference on parallel computing & transporter application, Amsterdam,1992. 12. Radcliffe N., Surry P. Formal memetic algorithm//Proceeding - Selected Papers from AISB Workshop on Evolutionary Computing.- P. 1-16 Springer-Verlag London, UK ©1994. 13. Dawkins R. The selfish gene.-Oxford: Oxford University press,1976. 14. Carlos Cotta, Pablo Moscato. Hand book of memetic algorithms. SpringerVerlag Heidelberg, 2012. 15. Herera F., Lozano M. Adaptation of genetic algorithm parametres based on fuzzy logic controllers// In F.Herera & J.Verdegay, editors. Genetic algorithms and soft computing, Physica-Verlag.- P.95-125. 16. Mitsuo G., Runwei C., Lin L. Network models and optimization.- SpringerVerlag London Limited,2008.-701p. 17. Hinterding R., Michalevicz Z., Eiben A. Adaptation in evolutionary computation: a survey//Proceedings of IEEE international conference on evolutionary computation, Piscataway, NJ:1997.-P.65-69. 18. Davis L.editor. Handbook of genetic algorithms.- New York.- Van Nostrand Rein-hold, 1991 2. 81 82 19. Juldstrom B. What have you done for me lately adapting operator probabilities in a steady-state genetic algorithm//Proceedings 6th international conference on Gas, San Francisco.-1995.-P.81-87. 20. Koumousis V.K., Katsaras C.P. Asow-tooth genetic algorithm combining the effects of variable population size and reinitialization to enhance performance//IEEE Transactions on Evolutionary Computation, 2006, 10(1).P.19-28. 21. L. Lin and M. Gen, “Auto-tuning strategy for evolutionary algorithms: Balancing between exploration and exploitation,” Soft Computing, vol. 13, pp. 157–168, 2009. 22. Moel M.C., Stewart C.V., Kelly R.B. Reducing the search time of a steady state genetic algorithm using the immigration operator//Proceedings IEEE International Conference Toolsfor AI.- 1991.-P.500-501. 82