VI Международная студенческая научная конференция Студенческий научный форум - 2014

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

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

Впервые идею использования генетического алгоритма для решения задач многокритериальной оптимизации предложил в своих работах Розенберг [3]. Однако в практической имплементации в биохимических экспериментах он свои идеи не реализовал. Практический метод был разработан Шаффером [4,5] и представлен в программе VEGA (Vector Evaluated Genetic Algorithm). В программе VEGA создаются подпопуляции одинаковой численности особей. Каждому n-у критерию Fnсоответствует подмножество подпопуляции хромосом Pnцелой популяции P. В каждой подпопуляции Pnвыполняется независимая селекция согласно критерию Fn.Однако ассоциация и скрещивание особей выполняется для всей популяции. Алгоритм VEGA можем представить следующим образом:

procedure VEGA;

begin

t := 0; инициализация начальной популяции P^t ;

оценка P^t;

while (not условие КОНЕЦ) do

begin

выполнить случайное разделение P^t на m подпопуляции

for (j =1,2,...,m) do

begin

T_j^t:=репродукцияP_j^t;

O_j^t:=генетические операторы T_j^t.

Оценка O_j^t;

P_j^t-1:=наследство (P_j^t,O_j^t)

P^t:= ∪_j=1^mP_j^t

end

t:=t+1;

end end.

В этом алгоритме селекция выполняется согласно так называемому турнирному методу. Причём «наилучшая» особь в каждой подпопуляции выбирается на основе своей функции приспособленности. Схематически алгоритм селекции с использованием «турнирного метода» при оптимизации двух функций представлен на Рис. 1., где F1 и F2 означают две разные функции приспособленности соответствующей оптимизируемой целевой функции. «Наилучшая» особь из каждой подпопуляции смешивается с другими особями и все остальные генетические операции производятся аналогично алгоритму при оптимизации одной функции [2].

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

Рисунок 1 – Алгоритм селекции при оптимизации двух функций

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

Библиографическийсписок

1. Гладков Л. А., Курейчик В. В, Курейчик В. М. и др. Биоинспирированные методы в оптимизации: монография. - М: Физматлит, 2009. - С. 384.

2. Рогачев А.Ф., Шубнов М.Г. Построение нейросетевых моделей прогнозирования временных рядов урожайности на основе автокорреляционных функций // Современные проблемы науки и образования. – 2013. – № 5; [Электронный ресурс] Режим доступа URL: www.science-education.ru.

3. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы. - 2-е изд. - М: Горячая линия-Телеком, 2008. - С. 452.

4. Rosenberg R.S. Simulation of genetic populations with biochemical properties, Mathematical Biosciences. 7. - P. 223–257.

5. Schaffer J.D. Multiple objective optimization with vector evaluated genetic algorithm // J.J. Grefenstete (Kd.): Genetic Algorithms and Their Applications. Proc. of the First Int. Conf. on Genetic Algorithms, Hillsdale, NJ: L. Eribaum. -1985. - P. 93-100.

Код для цитирования: Скопировать