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

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2002
1. Verfasser:	Сетлак, Г.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2002
Schriftenreihe:	Системні дослідження та інформаційні технології
Schlagworte:	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/50231
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Решение задач многокритериальной оптимизации с использованием генетических алгоритмов / Г. Сетлак // Систем. дослідж. та інформ. технології. — 2002. — № 3. — С. 32-42. — Бібліогр.: 15 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-50231
record_format	dspace
spelling	irk-123456789-502312013-10-09T03:05:13Z Решение задач многокритериальной оптимизации с использованием генетических алгоритмов Сетлак, Г. Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах В данной работе представлены существующие подходы и методы применения генетических алгоритмов для решения задач многокритериальной оптимизации. Предложены математическая модель и алгоритмы решения многокритериальной задачи выбора стратегии развития производственной системы. Представлены также результаты применения для решения этой задачи метода присваивания рангов Голдберга и гибридного генетического алгоритма. Представлені існуючи підходи і методи застосування генетичних алгоритмів для рішення залач багатокритеріальної оптимізації. Запропоновано математичну модель і алгоритми розв’язку багатокритеріальної задачі вибору стратегії розвитку виробничої системи. Навелено результати застосування для розв’язку цієї задачі методу надання рангів Голдберга і гібридного генетичного алгоритму. This paper describes the existing approaches and methods of application of genetic algorithms for multiobjective optimization. The mathematical model and algorithms for solving multiobjective optimization problems in management have been proposed. Experimental results of application of the hybrid genetic algorithms for solving combinatorial optimization problems have been presented. 2002 Article Решение задач многокритериальной оптимизации с использованием генетических алгоритмов / Г. Сетлак // Систем. дослідж. та інформ. технології. — 2002. — № 3. — С. 32-42. — Бібліогр.: 15 назв. — рос. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/50231 683.519 ru Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
spellingShingle	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Сетлак, Г. Решение задач многокритериальной оптимизации с использованием генетических алгоритмов Системні дослідження та інформаційні технології
description	В данной работе представлены существующие подходы и методы применения генетических алгоритмов для решения задач многокритериальной оптимизации. Предложены математическая модель и алгоритмы решения многокритериальной задачи выбора стратегии развития производственной системы. Представлены также результаты применения для решения этой задачи метода присваивания рангов Голдберга и гибридного генетического алгоритма.
format	Article
author	Сетлак, Г.
author_facet	Сетлак, Г.
author_sort	Сетлак, Г.
title	Решение задач многокритериальной оптимизации с использованием генетических алгоритмов
title_short	Решение задач многокритериальной оптимизации с использованием генетических алгоритмов
title_full	Решение задач многокритериальной оптимизации с использованием генетических алгоритмов
title_fullStr	Решение задач многокритериальной оптимизации с использованием генетических алгоритмов
title_full_unstemmed	Решение задач многокритериальной оптимизации с использованием генетических алгоритмов
title_sort	решение задач многокритериальной оптимизации с использованием генетических алгоритмов
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2002
topic_facet	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
url	http://dspace.nbuv.gov.ua/handle/123456789/50231
citation_txt	Решение задач многокритериальной оптимизации с использованием генетических алгоритмов / Г. Сетлак // Систем. дослідж. та інформ. технології. — 2002. — № 3. — С. 32-42. — Бібліогр.: 15 назв. — рос.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT setlakg rešeniezadačmnogokriterialʹnojoptimizaciisispolʹzovaniemgenetičeskihalgoritmov
first_indexed	2025-07-04T11:48:29Z
last_indexed	2025-07-04T11:48:29Z
_version_	1836716874784571392
fulltext	© Г. Сетлак, 2002 32 ISSN 1681–6048 System Research & Information Technologies, 2002, 3 УДК 683:519 РЕШЕНИЕ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ Г. СЕТЛАК В данной работе представлены существующие подходы и методы применения генетических алгоритмов для решения задач многокритериальной оптимизации. Предложены математическая модель и алгоритмы решения многокритериальной задачи выбора стратегии развития производственной системы. Представлены также результаты применения для решения этой задачи метода присваивания рангов Голдберга и гибридного генетического алгоритма. ВВЕДЕНИЕ Главная идея эволюционного моделирования — замена процесса моделирования сложного объекта процессом моделирования его эволюции. Она и сейчас привлекает учёных многих научных направлений [3]. Генетические алгоритмы, впервые представленные Холландом и его группой, развивались параллельно и независимо от методов эволюционной стратегии и эволюционного программирования. Незначительно отличаясь от эволюционного моделирования, они также основывались на теоретических достижениях теории эволюции, учитывающей механизмы наследования признаков в природных популяциях организмов и на накопленном человечеством опыте в селекции. В их основе лежат также генетические процессы биологических организмов, биологические популяции которых развиваются в течение нескольких поколений, подчиняясь законам естественного отбора и принципу «выживает наиболее приспособленный» [11]. Подражая этому процессу, генетические алгоритмы способны «развивать» решения реальных задач, если те соответствующим образом закодированы. По своей природе генетические алгоритмы относятся к классу процедур случайного поиска, который, однако, не сводится к совершенно беспорядочному блуждению в поисковом пространстве допустимых решений, благодаря способности эффективного использования опыта, приобретённого каждой популяцией в определении новой области поиска решений, в которой предполагается улучшение значения целевой функции. В течение последних двух десятилетий генетические алгоритмы в многочисленной библиографии используются как процедура поиска глобального оптимума при решении различных оптимизационных задач, благодаря чему их признали как один из наиболее мощных инструментальных средств в этом направлении [2, 3, 7, 9, 12]. В данной работе представлены методы и подходы применения генетических алгоритмов для решения задач многокритериальной оптимизации, а также предложено использование гибридного генетического Решение задач многокритериальной оптимизации с использованием генетических алгоритмов Системні дослідження та інформаційні технології, 2002, 3 33 алгоритма для решения многокритериальной задачи выбора стратегии развития производственной системы. 1. ОСНОВНЫЕ ПОНЯТИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ Существует ряд генетических алгоритмов, разработанных и используемых для решения различных оптимизационных задач [1, 6, 7, 11]. В большинстве случаев они мало похожи на тот простой генетический алгоритм, который впервые был описан Голдбергом на основе работ Холланда [4, 9]. По этой причине в настоящее время под термином «генетические алгоритмы» скрывается не одна модель, а очень большой класс алгоритмов, часто мало похожих друг на друга. Исследователи реализовали в своих работах различные типы генетических операторов кроссовера и мутации, специальных операторов, а также различные подходы к воспроизводству и отбору. Механизм каждого генетического алгоритма, однако, всегда состоит из трёх основных операторов: Репродукция — процесс, в котором хромосомы копируются согласно их целевой функции. Биологи называют эту функцию «пригодность» или «полезность», известную во многих публикациях как «fitness». Выбираются хромосомы с «лучшим» значением целевой функции. Оператор репродукции является искусственной версией натуральной селекции, т.е. выживанием сильнейших согласно теории Ч. Дарвина. • Кроссовер (crossover — иногда называемый рекомбинацией) — скрещивание родительских пар, генерация потомков. • Мутация — действие случайных воздействий. Рассмотрим схему функционирования стандартного генетического алгоритма, обычно используемого в оптимизационных задачах. 1. Выбор необходимого чётного числа K решений (особей) в популяции. Инициировать начальный момент времени 0=t . 2. Сформировать случайным образом начальную популяцию 0P , состоящую из К особей. 3. Оценка решений 0Px∈ согласно функции приспособленности. Для этого необходимо вычислить приспособленность каждой особи =)(xF (x)fitness= , ki ,...,1= и популяции в целом )(Pfitness 0=)(xFt . 4. Проверка условия ОСТАНОВ, если выполняется, то КОНЕЦ. 5. Выбирается с определенной вероятностью К особей с высокой приспособленностью из предыдущего поколения для скрещивания, записывается в банке генов GP. 6. Случайную селекцию 2/K родительских пар типа А и В из банка генов GP и с определенной вероятностью )(xp , зависимой от )(xf , поместить во временной популяции TP. 7. Скрестить выбранные родительские пары типа А и В из банка генов GP с вероятностью скрещивания cP и получить потомков типа C и D. 8. Поместить 2/K потомков типа C и D во временную популяцию TP. Г. Сетлак ISSN 1681–6048 System Research & Information Technologies, 2002, 3 34 9. С определенной (малой) вероятностью mP выполнить оператор мутации на особях из временной популяции TP, причём cm PP << . 10. Поместить полученную хромосому в новую популяцию TPP = . 11. Выполнить операции, начиная с пункта 3, k раз. 12. Увеличить номер текущей эпохи 1+= tt . 13. Если выполнилось условие ОСТАНОВА, то завершить работу. Иначе переход на шаг 3. 2. МЕТОДЫ ПРИМЕНЕНИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ 2.1 Постановка классической задачи многокритериальной оптимизации (МО) Рассмотрим общий случай векторной многокритериальной задачи. Найти [ ])(,...,)(),()(min 21 xfxfxfxf k= . (1) Здесь T ni xxxxx ],...,,...,,[ 21= — вектор решений, ni ,...,2,1= , n — количество переменных; Xx∈ , где nRX ⊂ — множество допустимых решений; )(xf j — j -й критерий оценки, kj ,...,2,1= . Вектор )(xf называем критериальным вектором, а kRYXf ⊂=)( — множеством допустимых оценок, где kR — критериальное пространство. Поскольку МО заключается в поиске оптимального решения, удовлетворяющего одновременно более чем одной целевой функции, то для нахождения компромиссного решения в многокритериальных моделях в теории оптимизации введено понятие решения оптимального по Парето, которое известно также как неулучшаемое решение или решение недомини- рованное. Формальное определение Парето-оптимального решения задачи МО дадим следующим образом [13]. Вектор Xx∈ называют Парето-оптимальным решением задачи (1) тогда и только тогда, когда не существует другого вектора решений Xx ∈* такого, что )()( * xfxf jj ≤ для kj ,...,2,1= , причём хотя бы для одного j это ограничение выполняется строго. Для решения такого вида задач МО разработаны различные методы и подходы, которые используют традиционные техники оптимизации и поиска решений. Одним из таких хорошо известных методов является метод, объединяющий оптимизируемые критерии в одну целевую функцию с использованием взвешенной суммы этих критериев, взятых с определёнными весами. Другой подход известен под названием «метода функции расстояния» (Method of distance functions). Так как генетические алгоритмы хорошо зарекомендовали себя в качестве методик поиска в больших областях практически при полном Решение задач многокритериальной оптимизации с использованием генетических алгоритмов Системні дослідження та інформаційні технології, 2002, 3 35 отсутствии информации о свойствах целевой функций и ограничений, в различных исследованиях было разработано несколько методов и подходов использования генетических алгоритмов для решения МО. Впервые идею использования генетического алгоритма для решения задач МО предложил в своих работах Розенберг [14]. Однако в практической имплементации в биохимических экспериментах он свои идеи не реализовал. Практический метод был разработан 17 годами позднее Шаффером [15] и представлен в програме VEGA (Vector Evaluated Genetic Algorithm). Шаффер модифицировал стандартный генетический алгоритм GENESIS Грефенстита [5], разработанный для однокритериальной оптимизации таким образом, чтобы можно было его применить для решения МО. 2.2 Метод независимой селекции Шаффера В программе VEGA создаются подпопуляции (subpopulations) одинаковой численности особей. Каждому n-у критерию nF соответствует подмножество подпопуляции хромосом nP целой популяции P. В каждой подпопуляции nP выполняется независимая селекция согласно критерию nF .Однако ассоциация и скрещивание особей выполняется для всей популяции. Алгоритм VEGA можем представить сдедующим образом: procedure VEGA; begin t := 0; инициализация начальной популяции tP ; оценка tP ; while (not условие КОНЕЦ) do begin выполнить случайное разделение tP на m подпопуляции for ( mj ,...,2,1= ) do begin =:t jT репродукция t jP ; =:t jO генетические операторы t jT . Оценка t jO ; =+ :1t jP наследство ( t j t j OP , ) ∪m j t j t PP 1 : = = end 1: += tt ; end end. Генетический алгоритм, используемый для решения задач МО в программном пакете FlexTool [6], основан на вышепредставленном подходе. В этом алгоритме селекция выполняется согласно так называемому Г. Сетлак ISSN 1681–6048 System Research & Information Technologies, 2002, 3 36 турнирному методу. Причём «наилучшая» особь в каждой подпопуляции выбирается на основе своей функции приспособленности. Схематически алгоритм селекции с использованием «турнирного метода» при оптимизации двух функций представлен на рис. 1., где 1F и 2F означают две разные функции приспособленности соответствующей оптимизируемой целевой функции. «Наилучшая» особь из каждой подпопуляции смешивается с другими особями и все остальные генетические операции производятся аналогично алгоритму при оптимизации одной функции. Алгоритм, представленный на рис.1, можно без труда преобразовать и расширить для оптимизации большего числа оптимизированных функций. Программный пакет FlexTool позволяет оптимизировать одновременно четыре функции. Недостатком метода Шаффера есть то, что в нём не учитываются промежуточные решения, оптимальные в смысле Парето, которые являются допустимыми для всех критериев, но не удовлетворяют какому-либо из скалярных критериев. Метод независимой селекции довольно прост и удобен для программной реализации (имплементации), а число новых популяций, необходимых для определения недоминированных решений, невелико. Поэтому он часто используется в исследованиях совместно с различными приближёнными методами. N особей популяции P(k) Подгруппа 1 (ПП1) Подгруппа 2 (ПП2) Расчёт функции приспособленности F2 для особей подгруппы 2 Расчёт функции приспособленности F1 для особей подгруппы 1 Выбор наилучшей особи в ПП1 Выбор наилучшей особи в ПП2 Формирование родительской группы М(К) и N особей Рис. 1. Решение задач многокритериальной оптимизации с использованием генетических алгоритмов Системні дослідження та інформаційні технології, 2002, 3 37 2.3 Метод присваивания рангов Голдберга Метод рангов Голдберга основан на методе приписывания рангов Бекера для однокритериальной оптимизации [1]. Согласно основной концепции оптимальности в смысле Парето, все особи в каждой популяции должны обладать одинаковым потенциалом репродукции. Для выполнения этого условия, Голдберг [9] «сортирует все особи по степени недоминирования», присваивает ранги следующим образом: • сначала рассматривается вся популяция, определяется множество недоминирующих решений в смысле Парето и всем этим недоминирующим особям в текущей популяции (выборке); присваивается ранг 1 и помещают их во главе списка; • затем рассматривается остальная часть популяции и ищется среди них следующая партия недоминирующих особей; присваивается им ранг 2; • процесс этот повторяется до момента рассмотрения и оценки всех особей в популяции; • предполагая, что для данной популяции было выгенерировано R подпопуляций и присвоены им различные ранги, функцию приспособ- ленности можно рассчитать по следующей формуле: 1)()( ++−= rxrxf , где )(xr — ранг популяции недоминирующих решений x. При небольшом числе решений в популяции или при малом различии решений может случиться, что число подпопуляций с разными рангами будет небольшим, что, в свою очередь, может привести к тому, что новые популяции не будут перемещаться по направлению к точке наилучшего множества оценок задания оптимизации. Чтобы избежать такой ситуации и обеспечить различие в решениях популяции, метод присваивания рангов необходимо использовать совместно с техникой формирования ниш и генотипов. Метод присваивания рангов Парето-оптимальным решениям характеризуется более высокой сложностью вычислений, чем метод селекции Шаффера [2, 9], так как для его реализации необходимо выполнить дополнительно )( 2 RKO операций с целью определения множества решений в смысле Парето. 2.4 Гибридный генетический алгоритм HAG Гибридный генетический алгоритм HAG разработан группой исследователей и предложен для решения многокритериальных комбинаторных задач распределения работ в многопроцессорных компьютерных системах [2]. Независимо от этих работ, был разработан подобный нейронно- эволюционный алгоритм для решения проблемы определения максимального потока во взвешенном графе [12], что бесспорно подтверждает правильность выбранного направления исследований повышения качества алгоритмов глобальной оптимизации. В настоящих исследованиях используется главная идея гибридизации генетических алгоритмов и совместное их использование как с нейронными сетями, так и с выбранными аналитическими методами оптимизации. Г. Сетлак ISSN 1681–6048 System Research & Information Technologies, 2002, 3 38 В гибридном алгоритме, подробно описанном ниже, для нахождения субоптимальных решений данной проблемы глобальной оптимизации используется аналитический метод оптимизации. Это действие может быть выполнено при помощи нейронной сети. Такой гибридный нейронно- генетический алгоритм представлен в публикациях [2, 8]. В нем для нахождения субоптимальных решений данной многокритериальной задачи используется нейронная сеть Хоппфилда. Гибридный алгоритм МО заключается в выполнении следующих действий: 1. Генерация начальной популяции P, имеющей K начальных решений )0(x . 2. Параллельное применение оптимизационного метода для К заданных начальных решений в популяции. 3. Определение матриц оценок ][ nkFY = на основе полученных субоптимальных решений x* при помощи стандартного оптимизационного метода. 4. Присваивание ранга к для начальных состояний x(0) на основе матрицы оценок Y. 5. Проверка выполнения критерия окончания поиска КОНЕЦ. 6. Случайный выбор начальных состояний в банке генов GP с использованием рангов. 7. Обнуление (очистка) текущей популяции ТР. 8. Случайная селекция 2/K пар родителей типа А и В из банка GP и перемещение их в текущую популяцию TP с вероятностью cp . 9. Скрещивание 2/K родителей A и В с высокой вероятностью cp и вставка К пар потомков типа С и D в текущую популяцию TP. 10. Мутация случайно выбранных особей из текущей популяции TP c малой вероятностью cm pp .. . 11. TPP =: . 12. Переход к шагу 2. 3. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧ МО Для анализа и оценки применения методов присваивания рангов Голдберга и представленного выше гибридного генетического алгоритма для МО используем следующую многокритериальную задачу. Предположим, что некоторая фирма изготавливает определенные i видов изделий, на которые определён спрос покупателей. В предприятии предусматривается освоение нескольких инновационных вариантов развития предприятия (это могут быть передовые технологии, обеспечивающие более эффективное функционирование производственной системы и увеличивающие производственные мощности и др.). Каждый вариант j ( mj ,...,2,1= ) характеризуется параметрами jrc , Sr ,...,2,1= , где S — продолжительность реализации варианта j Решение задач многокритериальной оптимизации с использованием генетических алгоритмов Системні дослідження та інформаційні технології, 2002, 3 39 (предполагаем что продолжительность одна и та же для всех вариантов). Здесь jrc — финансовые средства, необходимые для реализации j-го варианта в r-м году (периоде) с момента начала работы над этим вариантом развития. Планирование развития производственной системы в каждом периоде не должно превышать имеющихся фондов. В этой модели учитываются следующие переменные: • логические переменные }1,0{∈jtx определяют, следует ли начинать в периоде t реализацию варианта j (при 1=jtx ) или нет (при 0=jtx ); • iP — предполагаемый спрос на i-й тип изделия; • ijx — зависимость производства i-го типа изделия от внедрения j-го варианта развития производства, т.е. 1=ijx , если производство i-го изделия начато в результате введения j-го варианта развития производства, 0=ijx , если эти процессы независимы. Необходимо определить такую стратегию развития предприятия, которая обеспечивала бы непрерывное удовлетворение спроса, не приводила бы к превышению предоставляемых финансовых фондов и минимизировала бы суммарные затраты. Для упрощения не принимаем во внимание ни дисконтирование, ни износ, ни свертывание мощностей. Первый критерий означает минимизацию всех суммарных затрат, понесенных на внедрение выбранного варианта развития производства.: min 1 1 1 → ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ∑ ∑ ∑ = = = T t m j S r jtjr xc . (1) Второй критерий означает максимальное удовлетворение спроса на изготавливаемую продукцию i-го типа изделий, производство которой было начато в результате внедрения j-го варианта развития производства ( ) max 1 1 →∑ ∑ = = m j n i iji xp . (2) При этом Ttmjx jt ,...,2,1;,...,2,1},1,0{ ==∈ , ;,...,2,1},1,0{ nixij =∈ .,...,2,1 mj = А также должно быть выполнено следующее ограничение: ,1 1 =∑ = m j jtx Tt ,1= , показывающее, что в период времени t может быть реализован только один вариант развития производственной системы. Описанная выше задача является многокритериальной задачей комбинаторной оптимизации. Учитывая представленные выше ограничения, хромосому можем закодировать следующим образом: ( )Ttij xxxxX ,...,,,..., 111= , где jxt = , если j-й вариант развития был реализован в t-м году для Ttmj ,...,2,1;,...,2,1 == . Хромосома содержит ( ji *2+ ) генов. Для Г. Сетлак ISSN 1681–6048 System Research & Information Technologies, 2002, 3 40 решения вышепредставленной задачи необходимо сначала закодировать решение (хромосому). Если решаем задачу МО без ограничений, то можна хромосомы закодировать бинарно. А поскольку рассматривается общая постановка задачи, содержащей ограничения, используем для кодирования код Грея, позволяющий более эффективный поиск в области решений, чем бинарное кодирование (он обладает свойством непрерывности бинарной комбинации: изменение кодируемого числа на единицу соответствует изменению кодовой комбинации только в одном разряде). Процедура конверсии между натуральным кодом бинарным и кодом Грея может быть представлена следующим образом: пусть b — бинарный код, тогда 2)DIVbXORbg (= [3]. В предварительных исследованиях были выполнены тесты выше- представленной задачи со следующими параметрами: • оценивались три варианта развития производственной системы, т.е. 3=j ; • рассматривался временной период 3=T ; • принято количество производимых изделий, зависящих от внедрения j-го варианта 5=i . С учетом принятого были выбраны следующие параметры генетического алгоритма: • количество генов — 11; • вероятности мутации, инверсии и кроссовера подбирались экспериментально: вероятность мутации — 0,1; вероятность инверсии — 0,1; вероятность кроссовера — 0,7; • использовался турнирный метод отбора пар для кроссовера; • использовалась стандартная одноточечная операция скрещивания. На рис. 2 представлены результаты решения задачи развития производственной системы при помощи вышеописанного генетического алгоритма для МО, в котором применяется метод присваивания рангов Голдберга недоминирующим решениям. Метод присваивания рангов Голдберга приводит к тому, что в принятой начальной популяции производится поиск пространства оценок по направлению к границам Парето. Одновременно с возрастанием номера популяции (см. рис. 2) производится определение представителей актуально недоминирующих решений (штриховая кривая). Таким образом, рассматриваются все направления поиска и не дискриминируются промежуточные решения, оптимальные в смысле Парето, которые являются допустимыми для всех критериев, но не удовлетворяют какому-либо из скалярных критериев. Для решения задачи использовался программный пакет FlexTool [6]. Использование нейронной сети Хоппфилда в гибридном генетическом алгоритме для определения субоптимальных решений приводит к достижению параллельности, что понижает вычислительную сложность проблемы. Решение задач многокритериальной оптимизации с использованием генетических алгоритмов Системні дослідження та інформаційні технології, 2002, 3 41 ВЫВОДЫ В данной работе были приведены существующие подходы и методы применения генетических алгоритмов для решения задач МО, а также разработаны математическая модель и алгоритмы решения многокритериальной задачи выбора стратегии развития производственной системы. Представлены результаты применения для решения этой задачи метода присваивания рангов Голдберга и гибридного генетического алгоритма. На основании выполненных исследований и анализа полученных результатов можно сделать вывод, что генетические алгоритмы являются достаточно мощным математическим инструментом и могут с успехом применяться для решения широкого класса прикладных задач, включая те, которые трудно или даже вообще невозможно решить другими методами, а прежде всего таких задач, математическая модель которых не структурируема (неизвестна). ЛИТЕРАТУРА 1. Baker J.E. Adaptive selection methods for genetic algorithms, Proc. of an International Conference on Genetic Algorithms and their Applications. — 1985. — P. 101–111. Рис. 2 Г. Сетлак ISSN 1681–6048 System Research & Information Technologies, 2002, 3 42 2. Balicki J., Kitowski Z. Genetic-neural multiobjective optimization for resource allocation problems. Proceedings of the International Conference on Intelligent Technologies in Human-related Sciences, Leon. Spain. — 1996. — P. 18–22. 3. Cytowski J. Algorytmy genetyczne. Podstawy i zastosowania. AOW PLJ. — Warszawa. — 1996. 4. Holland J.H. Adaptation in Natural and Artificial Systems. Ann Arbor: The University of Michigan Press, 1975. 5. Grefenstette J.J. GENESIS: A system for using genetic search procedures. Proceedings of the 1984 Conference on Intelligent Systems and Machines, 161– 165 p. 6. FlexTool. Flexible Intelligence Group, L.L.C., Tuscaloosa, AL35486-1477, USA. 7. Fonseca C.M., Fleming P.J. An overview of evolutionary algorithms in multiobjective optimization, Evolutionary Computation. — 1995. — 3, N l. — P. 1–16. 8. Funabiki N., Kitamichi J., Nishikawa S. An evolutionary neural networks algorithm for max cur problems. Proceedings of the IEEE International Conference on Neural Networks. — Houston, Texas. — 1997. — P. 945–951. 9. Goldberg D.E Genetic algorythms in search, Optimization and Machine Learning. — Addison-Wesley P.C. — 1989. 10. Goonatilake S., Treleaven P. (red.). Intelligent Systems for Finance and Bussiness. — Chichester: Willey&Sons. — 1995. — 285 p. 11. Исаев С. А. Разработка и исследование генетических алгоритмов для принятия решений на основе многокритериальных нелинейных моделей. Автореф. дис. канд. техн. наук. — Н. Новгород, 2000. 12. Michalewicz Z. Genetic algorithms + Data structures = Evolutionary Programs. — Springer Verlag, 1992. 13. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. — М.: Наука. — 1982. — 254 с. 14. Rosenberg R.S. Simulation of genetic populations with biochemical properties, Mathematical Biosciences. 7. — P. 223–257. 15. 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. Поступила 02.10.2002

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

Institution

Ähnliche Einträge