Генетические алгоритмы

Генетические алгоритмы Существует следующая классификация эволюционного программирования: 1) эволюционные алгоритмы 2) генетические алгоритмы 3) генетическое программирование Эволюционные алгоритмы включает в себя: воспроизводство, мутации и естественный отбор, эволюция идет сразу по всей популяции Пример задачи для эволюционного алгоритма: Найти максимум некоторой функции: y=f(x)=kx+a sin(x) В случае функции многих переменных найти глобальный максимум не просто. Стандартные методы оптимизации, типа градиентного спуска не позволяют найти глобальный оптимум, начиная с некоторой точки они сходятся к локальному максимуму или минимуму. Методы случайного поиска часто не приводят к хорошему решению. Эволюционный алгоритм моделирует биологическую эволюцию. Построение эволюционного алгоритма. Выбираются X1, ... Xn - n случайных значений аргумента – организмы популяции. Воспроизводство и мутации: От каждого организма Xi образуются Ki потомков. Кол-во потомков может быть различно, в разных вариантах алгоритма, в зависимости от его приспособленности. Потомки –образуются добавкой случайных величин. Xij =Xi + e, j=1,Ki e – величина мутации. Обычно e – нормально распределенная величина, среднее ее значение равно 0, дисперсия s2 i. Каждого организма дисперсия различна. Отбор: Удаляются наименее приспособленные, для примера по значению функции f(Xi)>f(Xj) , организм i считается более приспособленным. На каждом шаге меняются Ki и s2 i . Основное достоинство эволюционных алгоритмов – они не требуют преобразования задачи, какой-нибудь перекодировки. Генетические алгоритмы. Основной особенностью генетических алгоритмов является то, что при воспроизводстве кроме мутаций происходит генетический обмен двух организмов. Поэтому в генетических алгоритмах происходит эволюция на уровне отдельных организмов. Рассматриваются только примеры задач, легко допускающие битовые кодировки. Большинство таких задач NP-полные. Пусть размерность такой задачи N. Любая строка из нулей и единиц является некоторым решением задачи, среди которых нужно выбрать наилучшее по условию задачи. Пример задачи для генетического алгоритма – задача о рюкзаке, классическая NP-полная. Как задача распознавания, задача о рюкзаке формулируется следующим образом: (Из книги Гэри Джонсон ЭВМ и труднорешаемые задачи) В переводе на обычный язык задача формулируется так. Даны N предметов с заданными весами w1,…,wn и стоимостями: v1,…,vn. Можно ли выбрать часть из них в рюкзак, чтобы их суммарный вес был <=B, а суммарная стоимость >=K. Все возможные решения кодируются n-битовой строкой: 10110001,…,110, если i предмет взят , то i- бит равен 1 Оптимизация с учетом важности стоимости и веса. Добавляются два весовых коэффициента alpha, beta (alpha+beta=1, alpha>0, beta>0). Эти коэффициенты умножаются соответственно на суммарную стоимость и суммарный вес. Например, если идет группа альпинистов, для них не так важен вес, как взять более ценные вещи, поэтому оптимальное решение (1001,…0) может максимизировать значение критерия: 0,9 *Суммарная стоимость-0,1*суммарный вес. С другой стороны, для группы школьников в однодневном походе, наоборот, критерием оптимальности будет: 0,1*суммарная стоимость-0,9*суммарный вес. Для небольшой размерности найти оптимальное решение можно полным переборов всех вариантов от 000,...0 до 111,...1 с выбором строки с максимальным значением критерия. Функция вычисляющая значение критерия оптимальности в дальнейшем называется функцией приспособленности организма. Пусть int weights[MaxN]; int values[MaxN]; соответственно, массив весов и ценностей предметов, MaxN – максимально возможная размерность, N – текущая размерность для данной задачи. Функция приспособленности Fitness на языке Си имеет вид: float Fitness(char *inp) // inp – входная строка из нулей и единиц { int i; float k; k=0; for(i=0;if2) { if(x=Pvm) // true остается более приспособленный { for(k=0;kf2) { // первый приспособленнее if(x