Содержание к диссертации
Введение
Глава 1. Постановка и методы решения многоиндексных транспортных задач 9
1.1. Классическая транспортная задача 9
1.1.1. Постановка транспортной задачи 9
1.1.1. Свойства транспортной задачи 11
1.1.2. Методы решения классической транспортной задачи 13
1.1.3. Многокритериальные транспортные задачи 15
1.2. Многоиндексные транспортные задачи 16
1.2.1. Симметричные трех- и четырехиндексные транспортные задачи 19
1.2.2. Уменьшение числа индексов для многоиндексных транспортных задач 21
1.2.3. Методы решения многоиндексных задач 23
1.3. Генетические алгоритмы 24
1.3.1. Эволюционные вычисления и генетические алгоритмы 25
1.3.2. Генетический алгоритм (ГА) 26
1.3.3. Основные генетические операторы и их версии 28
1.3.4. Применение генетических алгоритмов для решения задач условной оптимизации 30
1.3.5. Применение генетических алгоритмов для решения задач многокритериальной оптимизации 34
1.3.6. Генетические алгоритмы для решения транспортных задач 36
Глава 2. Методы конструирования генетических алгоритмов для решения модифицированных транспортных задач (МТЗ) 42
2.1. Объект и цели исследования 42
2.2. Выбор алгоритма для решения МТЗ 45
2.3. Синонимичные решения 48
2.4. Анализ характеристик симметричных транспортных задач и их влияния на реализацию генетического алгоритма 49
2.5. Генетические операторы для решения МТЗ 52
2.5.1. Использование составных генетических операторов 53
2.5.2. Особенности реализации ГО для МТЗ с разным числом индексов... 54
2.5.3. Генетические операторы репродукции для четырехиндексных транспортных задач 56
2.6. Влияние вида ограничений МТЗ на реализацию генетического алгоритма для их решения 62
2.6.1. Условия разрешимости многоиндексных транспортных задач 62
2.6.2. Общее в генетических алгоритмах для решения задач с ограничениями разного типа 65
2.6.3. Различия в генетических алгоритмах для решения задач с ограничениями разного типа: процедура инициализации 67
2.6.4. Различия в генетических алгоритмах для решения задач с ограничениями разного типа: генетические операторы 70
2.7. Рекомендации по созданию реализации генетического алгоритма для произвольной МТЗ 73
Глава 3. Исследование свойств генетических алгоритмов с помощью вычислительного эксперимента 77
3.1. Программная реализация 77
3.1.1. Объектная структура программного обеспечения (ПО) 77
3.1.2. Основные возможности ПО 80
3.2. Определение параметров ГА 83
3.2.1. Постановка задачи определения параметров ГА 83
3.2.2. Гибридный алгоритм 87
3.2.3. Комбинация операторов мутации и скрещивания 90
3.2.4. Синонимичные решения 91
Глава 4. Решение прикладных задач на основе предложенных алгоритмов 95
4.1. Постановка задачи 95
4.1.1. Математическая модель 96
4.1.2. Анализ модели 102
4.1.3. Исходные данные задачи 103
4.2. Решение поставленной задачи 104
4.2.1. Настройки генетического алгоритма 104
4.2.2. Программная реализация 106
4.2.3. Интерпретация результатов Ill
Заключение 117
Список литературы 118
- Методы решения классической транспортной задачи
- Анализ характеристик симметричных транспортных задач и их влияния на реализацию генетического алгоритма
- Объектная структура программного обеспечения (ПО)
- Математическая модель
Введение к работе
Актуальность
Многие предприятия металлургии работают на привозном сырье, которое, как и их продукция, доставляется в основном железнодорожным транспортом. Затраты на транспортировку составляют до 20% стоимости как привозного сырья, так и продукции, вследствие высоких тарифов на железнодорожные перевозки. Значительное число поставщиков*и покупателей, большая.номенклатура сырья и конечной продукции, нестабильная ситуация- в отрасли - все это приводит к многовариантности решения задачи транспортировки, а также к возможности быстрого его изменения в связи с меняющимися обстоятельствами. Поэтому среди задач1 управления, возникающих на металлургическом производстве, часто встречаются задачи, математическая модель которых представляет собой модифицированную транспортную задачу. Это не только различные задачи транспортировки, но и, например, задачи распределения ресурсов и размещения производства, перспективного планирования и т.п.
В металлургической отрасли встречаются в основном многоиндексные транспортные задачи. Большое число расходных материалов, широкий сортамент продукции, множество поставщиков и покупателей редко приводимы к однопродуктовой классической модели. Например, в задаче транспортировки, которая часто возникает в металлургическом производстве, дополнительные индексы в модели могут появиться при оптимизации доставки: неоднородного продукта, взаимозаменяемых товаров, продукции с промежуточной обработкой или с использованием различных видов транспорта.
Под модифицированной транспортной задачей (МТЗ), в отличие от классической, далее будем подразумевать задачу транспортного типа, имеющую отличное от двух число индексов и систему линейных ограничений с единичными коэффициентами и ненулевыми правыми частями. При этом в общем случае критерий может быть не только не линейным, но и не единственным. Математические модели МТЗ обладают высокой гибкостью и поэтому используются для описания и решения широкого класса задач. Этот факт обусловливает большую практическую значимость решения различных МТЗ.
Особенностью математического описания многих проблемных ситуаций, возникающих на производстве, является то, что при построении математической модели некоторое количество специфических ограничений "остается за скобками", чтобы не перегружать модель. В таком случае появляется необходимость получения множества субоптимальных решений, из которого затем выбирается наилучшее в смысле явно не учтенных в модели факторов.
В диссертационной работе поставлена и решена на основе разработанного модифицированного генетического алгоритма задача отыскания множества субоптимальных решенийгдля различных типов МТЗ.
Цель работы
Целью работы* является^ разработка системы модифицированных генетических алгоритмов отыскания множества субпотимальных решений- класса трех- и четырех-индексных транспортных задач с линейным, нелинейным или агрегированным критерием оптимальности, возникающих на металлургическом производстве.
Задачи исследования
Для семейства многоиндексных транспортных задач провести исследование возможности создания универсального алгоритма, не зависящего от вырожденности постановки, принципа учета множества критериев и обеспечивающего нахождение нескольких близких к оптимальному решений.
Исследование влияния основных особенностей постановки задач класса трех- и четырехиндексных МТЗ на изменения» операторов генетического алгоритма (ГА).
Построение генетического алгоритма как обобщенного метода решения задач данного класса.
Разработка ГА для симметричных МТЗ с векторными правыми частями и его модификация для решения симметричных МТЗ с матричными правыми частями.
Создание на их базе ГА для решения несимметичных МТЗ с соответствующим числом индексов.
Исследование эффективности различных возможных модификаций полученного ГА.
Решение с помощью разработанных алгоритмов прикладной МТЗ для металлурги
ческого производства на примере условий Выксунского металлургического завода
(далее ОАО ВМЗ).
Методы исследования
Для решения поставленных задач были использованы методы системного анализа, исследования операций, теории графов, оптимизации, объектно-ориентированного программирования.
Научная новизна^ состоит в следующем: - На основе результатов проведенного анализа возможностей генетических алгоритмов создана система для решения указанного класса производственных задач.
' Доказана возможность создания^семейства эффективных алгоритмов решения для различных постановок-МТЗгна* основе ГА, используемого в качестве общего метода, который построен и программно реализован с использованием нового вида представления структуры генетического алгоритма.
На основе анализа класса многоиндексных транспортных задач выявлены существенные с точки зрения построения, универсальной системы их решения свойства, проанализировано влияние этих свойств нафеализацию основных процедур ГА.
Предложен и реализован гибридный генетический алгоритм для решения МТЗ с векторными правыми частями и исследована эффективность его применения.
Практическая значимость. Разработано программное обеспечение для решения широкого класса трех- и четырехиндексных транспортных задач на основе генетических алгоритмов, которое применено при решении задачи транспортировки сырья для ОАО ВМЗ, пригодное к использованию на предприятиях, имеющих аналогичную структуру поставщиков и транспортного парка. Разработанное программное обеспечение допускает использование в целях обучения для оценки сравнительной эффективности и изучения особенностей функционирования ГА.
Апробация результатов. Результаты диссертационной работы докладывались и обсуждались на:
ежегодных студенческих научно-технических конференциях МИСиС (Москва,
2001 и 2003 гг.);
семинарах на кафедре автоматизированных систем управления Московского государственного института стали и сплавов (технологический университет).
Публикации. Основное содержание диссертационной работы отражено в 5 печатных работах.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Общий объем работы 140 стр.
Методы решения классической транспортной задачи
Для решения классической» транспортной задачи было разработано достаточно большое число различных методов решения, основанных как на-основных методах решения общей задачи линейного программирования, так и на эвристических приемах учета особенностей» модели транспортной задачи [18, 19, 20, 24, 34, 40, 41, 47, 62, 63].
Методы решения классической транспортной задачи делятся на точные и приближенные методы. Приближенные методы, известные также как методы-нахождения опорного плана, позволяют за небольшое число шагов получить допустимое, но не всегда оптимальное, решение задачи. К данной группе методов относятся методы северо-западного угла, минимального элемента, аппроксимации Фогеля и нуль-преобразований [1, 20, 34, 56].
Точные методы позволяют найти оптимальное решение. Конечные методы решения транспортной задачи можно разделить на группы в соответствии с тем, на каком из методов решения общей задачи линейного программирования они основываются. Одна группа алгоритмов основана на наиболее популярном методе линейного программирования - методе последовательного улучшения плана, другая базируется на идеях метода последовательного сокращения невязок [20].
Первый точный метод решения транспортной задачи - метод потенциалов - был предложен в 1949 году Л.В. Канторовичем и М.К. Гавуриным. Этот метод является детализацией метода последовательного улучшения плана применительно к транспортной задаче [20]. Несколько позднее аналогичный алгоритм был разработан Данцигом, который исходил из общих идей линейного программирования. Этот метод является самым популярным алгоритмом для решения транспортных задач, его описание можно найти в [11, 24, 34, 51, 56, 60]. Метод потенциалов содержит в себе решение системы линейных уравнений, число которых равно числу ненулевых компонент опорного плана. В случае, если опорный план содержит меньше ненулевых компонент чем число линейно независимых уравнений системы ограничений задачи, то такой план называется вырожденным. В этом случае необходимо внести некоторые коррективы в алгоритм метода потенциалов. То есть, метод потенциалов чувствителен вырожденности, задачи, что может оказать существенное влияние на качество решения задач высокойфазмерности [56].
Вторым по популярности является венгерский метод. Идея этого метода была высказана венгерским-математиком Эгевари задолго до возникновения теории линейного программирования в 1931 г. [20]. Длительное время она оставалась малоизвестной. В 1953" г. американский математик Кун перевел ее на английский язык [20]. Он развил идею Эгевари № предложил «метод , названный им венгерским, для решения задачи выбора (частный случай, транспортной задачи) [40]. В дальнейшем метод был усовершенствован и перенесен на произвольную транспортную задачу [47, 62, 63]. Венгерский алгоритм относится ко второй группе конечных алгоритмов. Он не чувствителен к вырожденности задачи и не требует решения системы линейных уравнений. С другой стороны его логическая структура сложнее, чем в методе потенциалов [20].
К алгоритмам, основанным на методе последовательного улучшения плана, относится и алгоритм разработанный Глейзалом [18]. Этот алгоритм одинаково применим для решения как невырожденных, так и вырожденных задач, но его логическая структура также сложнее, чем в методе потенциалов [20].
Общим для всех этих алгоритмов является необходимость в матричном представлении целевой функции и то, что в результате они находят только одно решение. Все эти методы имеют существенные ограничения по применимости для решения задач с произвольной схемой учета нескольких критериев. Кроме того, единственность находимого решения является недостатком, когда кроме факторов, учтенных в математической модели, существует еще ряд параметров, учет которых не обязателен, но желателен при выборе конечного варианта решения. В таком случае решения, полученные данными методами, надо дополнять допустимыми решениями, полученными каким-то другим способом.
Для решения транспортных задач также предлагалось использовать конечные методы блочного программирования. В [69] описан конечный метод решения транспортной задачи, использующий идею метода разложения Данцига-Вульфа. Методы блочного программирования оказываются особенно полезны для решения задач, отягощенных дополнительными ограничениями общего вида [20]. То есть они применимы и эффективны только для некоторых частных постановок задач. 1.1.3. Многокритериальные транспортные задачи
В большинстве случаев требуется решить задачу, принимая во внимание больше чем один критерий, что приводит к многокритериальной транспортной задаче [7, 37, 38, 71, 82, 83, 84, 97, 102, 111]. Математические модели этих задач различаются стратегией учета многокритериальности, и, соответственно, отличается и алгоритм их решения.
В качестве критерия может выступать стоимость транспортировки, время доставки, количество доставляемых товаров, расход горючего, надежность и безопасность доставки - снижение стоимости единицы перевозимого продукта из-за потери качества, и многие другие [98].
Например, Bit, Biswal и Alam [73, 74] исследовали применение подхода нечеткого программирования к многокритериальной планарной транспортной задаче. При этом подходе целевые функции описываются как нечеткие множества, и множество решений определяется как пересечение всех нечетких множеств и ограничений. Правило отбора решений состоит в выборе решений, имеющих наибольшую степень принадлежности к множеству решений. Они использовали линейную функцию принадлежности.
В работах [71, 97] исследовалась граница множества Парето для бикритериаль-ной двухиндексной транспортной задачи. В этих работах предлагается итеративная процедура синтеза полной совокупности эффективных оценок.
Батищев, Коган и Шахриев исследовали многокритериальные двухиндексные задачи, возникающие при рассмотрении предпочтений и целей всех участвующих в транспортном процессе субъектов. Для нахождения решения многокритериальных задач исследовались методы главного критерия, лексикографический, лексикографический квазиоптимальности, минимального элемента и принцип гарантированного результата [7, 38].
Анализ характеристик симметричных транспортных задач и их влияния на реализацию генетического алгоритма
Использование "вертикального сходства" генетических операторов заключается в том, что идеи, заложенные в их реализациях для решения задач с одним числом индексов, можно переносить в реализации для решения задач с другим числом индексов. В п. 1.3.6 приведено описание существующих разработок по применению ГА для решения классической двухиндекснои и трехиндекснои трипланарнои транспортных задач. Однако, простой перенос алгоритмов на задачи с большим числом индексов в ряде случаев невозможен, и для задач с числом индексов четыре требуется разработка соответствующих генетических операторов, которая представляет собой отдельную задачу, решенную в данной работе, результаты которой описаны в п.2.5.3.
Остановимся более детально на тех случаях, когда перенос идей между генетическими операторами с разным числом индексов затруднен или невозможен. Классическая транспортная задача имеет ряд свойств, которые при увеличении числа индексов № сохранении общей специфики ограничений, тем не менее, не пере-носятся на случай большего числа индексов. Первым таким свойством является возможность представления» допустимого плана задачи в виде связанного дерева. Это свойство было весьма остроумно использовано в работе GEN и др.[89]. Попытки представить аналогичным образом допустимые планы, например, трехиндекных задач показывают, что на "транспортном графе" [89] образуются циклы. То есть, допустимые решения невозможно представить в виде связанного дерева [54], и использованное в работе кодирование с помощью числа Прюфера невозможно применять для задач с числом индексов более 2. Второе весьма полезное свойство классической задачи, использованное в работах [5, 118], состоит в том, что матрица, содержащая остаток от деления суммы двух опорных планов на два, в каждой строке и каждом столбце содержит четное число ненулевых элементов. Это свойство не присуще транспортным задачам с числом индексов более 2. В этом легко убедится как при рассмотрении матрицы решения по отдельным двумерным сечениям, так и при представлении многомерной матрицы решения размера, например, mxnxpxq, в виде двумерной матрицы размера (mq)x(np). При переходе от двухиндекснои задачи к трехиндекснои, и от трехиндекснои к четырехиндекснои увеличивается "разреженность " матрицы, то есть уменьшается доля ненулевых элементов. Этот факт понижает эффективность некоторых алгоритмов, связанных с отбором случайного числа компонент решения и разработанных изначально для классической транспортной задачи. Особенно остро эта проблема проявляется при "прямом переносе" подобных алгоритмов на случай многоиндексных задач, правые части которых являются одномерными массивами. 2.5.3. Генетические операторы репродукции для четырехиндексных транспортных задач В этой работе сконструированы и программно реализованы операторы репродукции для генетических алгоритмов решения транспортных задач с четырьмя индексами. Их описанию посвящен данный раздел. Описания реализаций генетического алгоритма для решения двух- и трехиндексных транспортных задач представлены в разделе 1.3.6. При»создании генетических операторов воспроизводства для четырех-индексного случая были модифицированы алгоритмы , представленные в [5, 75, 98, 100,103,118,121]. Мутация, ориентированная нафаботу с многомерными матрицами, имеет мало общего с классическими видами мутации: одно и двухточечной, инверсии и т.д. В данной работе построены следующие четыре модификации оператора мутации, описания и условные названия которых приведены ниже. Мутацией типа "Перераспределение" будем называть такую модификацию оператора мутации, при которой фиксируется случайное количество индексов по каждому из измерений матрицы родительской хромосомы; ее компоненты, соответствующие выбранным индексам, без изменения переносятся в хромосому потомка; остальные, невыбранные, компоненты считаются отсутствующими; затем вычисляются невязки хромосомы потомка; их объемы распределяются с помощью процедуры нахождения опорного плана; получаемый в этой процедуре план объединяется с уже имеющейся хромосомой потомка. Схематическое изображение данного вида мутации представлено на рис.8. Частным случаем мутации типа "перераспределения" является мутация, которая далее будет обозначаться-"перераспределение %". Отличие в том, что для перераспределения выбираются только те компоненты решения, которые соответствуют наибольшим коэффициентам целевой функции. Их число задается некоторым процентом от общего числа переменных. Для удовлетворительного результата, в случае, когда решается задача небольшой-размерности, процент перераспределяемых величин» необходимо подобрать так, чтобы число перераспределяемых компонент было не менее двух, в противном случае потомок данного вида мутации эквивалентен родителю.
Для внесения изменений, при сохранишосновной информации, содержащейся в хромосоме, созданы еще два одинаковых по механизму алгоритма мутации - мутации типа "переменные изменения" и "минимальные изменения".
Объектная структура программного обеспечения (ПО)
Программная реализация результатов гл. 2 создана на языке Object Pascal в среде Delphi с использованием технологии объектно-ориентированного программирования:1 В основе ПО лежит объектное представление генетического алгоритма, являющееся детализацией принципа разделения процедур ГА по области действия, приведенного в п.2.4 и проиллюстрированном на рис.5. Объектная структура генетического алгоритма для решения семейства МТЗ показана на рис. 16. Данная объектная структура состоит из 4 основных классов: Problem, Population, Individ и Solver, назначение которых указано ниже. Класс Problem предназначен для хранения условия решаемой задачи. Здесь реализованы те части генетического алгоритма, которые зависят от типа решаемой задачи - процедуры Initialization, Mutation и Crossover. Класс Individ описывает особь генетического алгоритма и в случае однокритери-альной постановки состоит из варианта решения задачи и соответствующего ему значения» целевой функции. Класс Population представляет собой объект, состоящий из множества особей, и содержащий в себе ссылку на решаемую задачу, в нем реализованы процедуры работы с особями и популяцией в целом. Он содержит в себе методы, которые соответствуют процедурам Evaluate и Replace генетического алгоритма, а также несколько вспомогательных методов (например, сортировка популяции в порядке возрастания значения функции пригодности) и служебных полей. Класс Solver нужен для связи между решаемой задачей и популяцией возможных решений. Экземпляр этого класса создает популяцию и передает ей указатель на решаемую задачу. В этом классе реализован отбор особей и последовательный вызов всех процедур генетического алгоритма. Данная объектная структура обеспечивает удобство разработки, реализации и отладки множества реализаций генетического алгоритма для решения различных МТЗ, то есть является по существу структурой обобщенного алгоритма решения указанного класса задач. Универсальность обобщенного алгоритма обеспечивается с помощью класса Problem, схема наследования свойства которого показана на рис.17. Наследники класса Problem представляют собой объекты, содержащие в себе реализации тех процедур ГА, которые зависят от специфики решаемой задачи. Схема наследования свойств построена с учетом "вертикального" и "горизонтального сходства" генетических операторов для разных МТЗ. Все экземпляры класса Problem содержат уникальную процедуру Create, ответственную за создание условий решаемой задачи - матрицы коэффициентов целевой функции и правых частей ограничений. Объекты ТЗ и Т4 носят вспомогательный характер, в них реализуются те части ГО, которые являются общими для задач с данным числом индексов. Части ГО, ответственные за расчет невязок, как зависящие от структуры ограничений задачи, реализованы в соответствующих процедурах дочерних классов. Процедура CreateSolution отвечает за нахождение допустимого плана задачи и поэтому также реализуется в каждом конкретной случае заново. Такой подход обеспечивает унификацию процедур решения различных типов задач и уменьшает количество программного кода, а вместе с ним и ошибок. При этом! есть возможность описания различных механизмов мутации и скрещиванитдля-разных задач, что увеличивает гибкость системы и позволяет исследовать алгоритмы решенияфазных типов задач независимо друг от друга. Структура класса Problem и распределение процедур, составляющих генетический алгоритм, по объекту манипулирования позволяют легко добавлять новые типы транспортных задач. Рекомендации по созданию реализаций ГА для произвольной МТЗ приведены в п. 2.7. Наследник класса Problem, который будет содержать созданные согласно этим рекомендациям процедуры Create, CreateSolution, Mutation и Crossover является дос-таточньїмі изменением систем-- для обеспечения решения дополнительного, ранее не решаемого, типа МТЗ. Таким образом, объектная структура ПО в целом, и класса Problem в частности, позволяет как исследовать единые механизмы решения разных типов задач, так и создавать специализированные версии алгоритма для решения конкретных типов. В программном обеспечении для решения различных типов МТЗ реализованы следующие функции: создания файла условий задачи; редактирования файла условий; решения задач с помощью соответствующей модификации ГА; тестирования различных параметров генетического алгоритма (для некоторых типов задач); сохранения результатов решения и тестирования в текстовом файле. Для начала работы необходимо запустить файл OopTransGA.exe. Выбрать в строке меню пункт "Open" и в окне всплывающего диалога открытия файла указать путь и выбрать нужный файл условия. На основной форме приложения отобразится информация о решаемой задаче: тип, размерность и число допустимых решений, рассчитанное по формуле (3.2).
Файл условия- представляет собой текстовый файл MS Windows, который создается при выборе пункта "Create" в1 строке меню. Внешний вид окна создания условий представлен на рис. 18 а. В правом верхнем углу расположен выпадающий список, содержащий перечисление реализованных для решения типов МТЗ. Для каждого из типов отображается математическая модель и создается соответствующая маска для ввода числовых данных. После завершения ввода необходимо нажать кнопку "Сохранить" и указать в окне появившегося диалога путь и имя создаваемого файла условий.
Математическая модель
Увеличение численности популяции приводит к возростанию числа мутаций и скрещиваний, следовательно, ускоряет движение популяции в сторону оптимума. С другой стороны, при значительном увеличении числа особей, принимающих участие в поиске, при достижении некоторого предела возникает так называемый "комбинаторный взрыв" - резкое увеличение времени вычислений. Величина этого предела зависит от вычислительной мощности применяемой техники.
13. Тип инициализации. Начальная популяция всех построенных в данной работе генетических алгоритмов состоит только из допустимых решений. Ее можно сформировать несколькими способами. Первый - создать популяцию из случайного набора решений, получаемых, например, с помощью процедуры нахождения допустимых планов со случайным выбором минимального элемента. Второй - получить некоторое подобие равномерного распределения, взяв достаточно большого размера случайную популяцию и удалив из нее дублирующиеся особи. Проблема в том, что, как было показано ранее, число целочисленных вершин многоиндексной задачи значительно, а при больших размерах начальной популяции наступает "комбинаторный взрыв", поэтому как таковое равномерное распределение начальной популяции проблематично. Третий вариант - создать начальную популяцию, состоящую из копий одной и той же, в некотором смысле хорошей особи. Это обеспечивается предлагаемым в работе гибридным генетическим алгоритмом.
Варианты генетических операторов воспроизводства. Для четырехиндексных задач с векторными правыми частями ограничений в данной работе сконструированы и реализованы 4 варианта мутации и 3 вида скрещивания, которые описаны в разделе 2.5.3. Обычно при решении МТЗ с помощью ГА используется только одна какая-либо комбинация генетических операторов обоснования выбора ее (см. п. 1.3.6). Поэтому данных о сравнительной эффективности применения различных ГО нет. 15. Оператор отбора и способ выбора родительской пары. Различные комбинации способов выбора родительских пар для скрещивания и отбора особей для формирования новой популяции регулируют преждевременную сходимость алгоритма к одному из возможных решений. Элитизм и линейное ранжирование имеют более высокую скорость сходимости, но в результате конечная популяция может состоять только из копий лучшей особи в данном поколении, что равносильно нахождению одного решения. Значительное увеличение числа поколений в этом случае может привести к нахождению другого решения , но не обязательно. В сочетании этих схем отбора с инбридингом вероятность того, что алгоритм покинет область локального оптимума, невысока. Отбор вытеснением позволяет получить в последней популяции не только оптимум, но и множество близких к нему различных решений. Наименьшее количество ресурсов (в смысле сложности вычислений) при прочих равных начальных условиях нужно генетическому алгоритму с комбинацией линейное ранжирование - селективный отбор. Все другие комбинации работают медленнее. Таким образом, выбор схемы отбора представляет собой многокритериальную задачу. Значения критериев качества функционированияТА. с различными схемами отбора зависят от специфики решаемой задачи. Для транспортных задач не проводилось достаточно исследований.
В свете выше сказанного возникает задача о нахождении оптимальных настроек генетического алгоритма для решения МТЗ с векторными правыми частями. Часть полученных результатов можно обобщить и распространить на ГА для решения МТЗ других типов. Гибридный алгоритм предложен в результате исследования выбора оптимального режима инициализации. Гибридным генетическим алгоритмом называется алгоритм, получаемый в результате объединения генетического алгоритма и специальных методов решения рассматриваемой задачи [21, 31]. Возможно два варианта гибридизации: специальные методы используют для нахождения приблизительных решений, которые затем улучшают генетическим алгоритмом, или наоборот, приблизительные решения нахо дятся с помощью генетического алгоритма, которые затем улучшают с помощью специальных методов. В данном случае прелагается гибридный генетический алгоритм для решения МТЗ с векторными правыми частями, в котором для отыскания особей начальной популяции используются приближенные методы решения соответствующей МТЗ. При этом процедура отыскания допустимых планов во всем остальном алгоритме остается неизменной. Для отыскания начальной популяции предлагается использовать метод минимального элемента (с поиском по всей матрице). Этот метод является наиболее эффективным из всех вариантов метода минимального элемента [56] и не уступает по эффективности другим приближенным методам решения транспортных задач [35, 56]. Область применимости предлагаемого гибридного генетического алгоритма совпадает с областью применимости метода минимального элемента для МТЗ. То есть область применимости содержит в себе постановки с векторными правыми частями, а также множество постановок с комбинацией ограничений с векторными и матричными правыми частями, для которых можно построить эффективную вариацию метода минимального элемента. Характерной особенностью генетических алгоритмов, построенных в данной работе, является быстрое продвижение в направлении минимума функции в течение первых N поколений и медленное уточнение найденных решений на последующих N итерациях. (Значения N и N зависят от конкретной постановки МТЗ, но подобная специфика наблюдалась для всех тестируемых типов задач.) При этом каждая реализация генетического алгоритма при заданных типах мутации, скрещивания и отбора и фиксированном размере популяции за число поколений N давала некоторое, в среднем постоянное в абсолютном и процентном выражении улучшение значения целевой функции относительно лучшей особи в начальной популяции. Поэтому качество работы алгоритма в течение первых N поколений зависит от качества начальной популяции, то есть, от ее близости к оптимуму. Опыты показали, что решения, найденные гибридным алгоритмом за ограниченное число поколений, в среднем на 20-40 % лучше, чем решения, найденные за то же число поколений, с помощью алгоритма со случайной инициализацией. (Опыты проводились при размере популяции 100-300 особей.) Был проведен эксперимент для получения ответа на вопрос: какого размера должна быть начальная популяция, сгенерированная случайным образом, чтобы получить лучшее значение функции приспособленности, близкое к значению, получаемому гибридным алгоритмом. В табл. 11 представлены результаты теста по сравнению эффективности процедур инициализации простого и гибридного генетического алгоритма. В ней приведены размерности тестовых задач и соотвествующие значения в начальной популяции, полученные с помощью гибридного алгоритма. Также приведены значения приспо-собленностей лучших особей в начальных популяциях, обнаруженные для этих же задач простым ГА при указанном размере популяции. Как следует из проведенных тестов и их результатов, представленных в табл. 11, гибридный генетический алгоритм имеет более эффективную процедуру инициализации, чем простой ГА при выбранных размерах популяции.
![Разработка методов, моделей и алгоритмов прогнозирования и донозологической диагностики кожных болезней, имеющих представительство на проекционных зонах, с использованием нечеткой логики принятия решений и рефлексодиагностики [Электронный ресурс]](/i/i/4381/168311.png "Разработка методов, моделей и алгоритмов прогнозирования и донозологической диагностики кожных болезней, имеющих представительство на проекционных зонах, с использованием нечеткой логики принятия решений и рефлексодиагностики [Электронный ресурс] Ходеев Денис Владимирович")
