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

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное

учреждение высшего профессионального образования

«Комсомольский-на-Амуре государственный

технический университет»

 

 

Факультет компьютерных технологий

Кафедра «Прикладная математика и информатика»

 

 

 

 

 

РЕФЕРАТ

по дисциплине «Дискретные математические модели»

Применение генетических алгоритмов к решению

задач дискретной оптимизации

 

 

 

 

 

 

Студент группы 3МИм-1   Я.А. Рассолова

Руководитель работы  Г.И. Коротеев

 

 

 

2014

Содержание

 

 

 

 

 

Введение

 

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

Генетические методы предназначены для решения прикладных экстремальных комбинаторных задач переборного типа (задачи о ранце, задачи о назначениях и др.), которые относятся к классу NP-трудных задач.

Генетический метод представляет собой скорее популяционно-генетический подход к решению задачи поиска, чем единый алгоритм решения дискретных оптимизационных задач. Таким образом, генетический метод образует класс алгоритмов поисковой оптимизации, основанных на математическом моделировании биологических механизмов и процессов в живой природе с помощью принципов популяционной генетики, которые позволяют находить оптимальные или близкие к ним (субоптимальные) решения.

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

Применение генетических методов для решения NP-трудных комбинаторных задач оптимизации полезно тогда, когда необходимый объем вычислительных затрат может оказаться большим, но скорость, с которой этот объем увеличивается при экспоненциальном росте «размерности» задачи дискретной оптимизации, часто может расти лишь линейно.

 

1 Постановки задач дискретной оптимизации

 

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

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

Задача оптимизации возникает тогда, когда имеется набор (вектор) внутренних параметров , который может принимать множество различных значений .Такие параметры принято называть управляющими переменными. Собственно в определении конкретных значений управляющих переменных и состоит акт принятия решения.

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

Управляющие переменные и характеристики определяют существенные свойства объекта исследования. При этом играют роль независимых переменных, а являются зависящими от них величинами . Множество будем называть областью поиска, а любой вектор – допустимым решением.

Оптимизационные задачи формулируются как проблема выбора лучшего допустимого решения. Для определения понятия «лучшего» часто приходится вводить критерий оптимальности (или не один, а несколько критериев оптимальности) – количественный показатель, посредством которого осуществляется объективное измерение в некоторой числовой шкале Y одного наиболее важного для исходной задачи выходного параметра . Под измерением по шкале понимается отображение , которое каждому решению ставит в соответствие числовую оценку таким образом, чтобы отношения между числовыми значениями сохраняли бинарные отношения предпочтения между решениями:

1.  «лучше»   () тогда и только тогда,

когда ;

2. «не хуже»   тогда и только тогда,         (1.1)

когда ;

3. «эквивалентно» тогда и только тогда,

когда .

 

Из соотношений (1.1) следует, что механизм выбора «лучшего» решения сводится к отбору тех и только тех решений, которые доставляют наибольшее значение критерию оптимальности Q в области поиска D:

 

,      (1.2)

где – оптимальное решение;    – наибольшее значение критерия оптимальности среди всех значений критерия   в области поиска .

Выражение (1.2) является математической записью модели принятия решения, называемой экстремальной задачей однокритериального выбора.

В том случае, когда область поиска состоит из счетного числа решений, принято говорить о задаче (1.2) как о задаче дискретной оптимизации.

Задача максимизации критерия является классической формой постановки задачи, к ней легко свести задачу, требующую минимизации критерия:

.       (1.3)

Переход к задаче максимизации можно осуществить, например, одним из трех способов:

,       (1.4)

, где  такое, что , ,    (1.5)

 

       (1.6)

 

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

, .       (1.7)

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

В случае унимодальной функции (или одноэкстремальной функции) оптимальное решение единственно и достигается в точке локального максимума:

,      (1.8)

где – -окрестность точки локального максимума .

Многоэкстремальная функция предполагает несколько локальных максимумов. Глобальный максимум – наибольший из всех локальных максимумов. По аналогии формулируются понятия локальный и глобальный минимумы для задач минимизации (1.3).

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

, .     (1.9)

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

Иногда в задачах дискретной оптимизации не удается выделить единственный наиболее важный выходной параметр, что приводит к многокритериальной постановке оптимизационной задачи:

       (1.10)

Каждый из критериев задачи (1.10) , где , называют частным критерием многокритериальной задачи оптимизации.

Из всего разнообразия подходов к решению многокритериальных задач отметим два. Первый заключается в сведении задачи вида (1.10) к задаче однокритериального выбора (1.2) методом свертки нескольких критериев в один обобщенный критерий. Другой подход предполагает введения новых отношений предпочтения, отличных от (1.1). Примером подобных отношений предпочтения могут служить отношения компромисса:

 

1. «лучше» тогда и только тогда, когда

  для любого   и существует

по крайней мере один частный критерий,

обращающий неравенство в строгое:

 ;

2. «не хуже»   тогда и только тогда, когда                           (1.11)

 для любого ;          

3.  «эквивалентно»   тогда и только тогда,

когда   для любого .

 

В случае отношений предпочтения (1.11) решением задачи будет уже не точка в пространстве поиска, но область из компромиссных решений.

 

2  Метод исчерпывающего  перебора и понятие задачи  переборного

    типа

 

В том случае, когда решение задачи (1.2) можно свести к анализу значений критерия оптимальности для конечного числа решений (1.3), говорят, что экстремальная задача однокритериального выбора относится к классу экстремальных задач переборного типа (или переборных задач).

      (1.12)

Здесь множество – конечно, и количество возможных решений равно N. В силу этого формально все допустимые решения можно пронумеровать: и поиск лучшего варианта из множества допустимых решений сводится к полному перебору. Именно этим обстоятельством объясняется название переборных задач.

 

3 Оценка трудности задач дискретной оптимизации

 

Назовем алгоритм эффективным, если он способен найти решение задачи за время, полиномиально зависящее от объема входной информации, а задачи, имеющие такой алгоритм, – полиномиально разрешимыми. Являются ли задачи переборного типа полиномиально разрешимыми? Чтобы ответить на этот вопрос, оценим объем перебора.

Так как допустимое решение задачи (1.12) является n-мерным вектором , каждый компонент которого может принимать одно из возможных значений из множества допустимых значений: то можно рассчитать нижнюю оценку мощности множества допустимых решений:

     (1.13)

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

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

 

4 Основные понятия о генетических алгоритмах

4.1 Природный механизм

 

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

Согласно теории эволюции Чарльза Дарвина, особи популяции конкурируют между собой за ресурсы (пищу) и за привлечение брачного партнера. Те особи, которые наиболее приспособлены к окружающим условиям, проживут дольше и создадут более многочисленное потомство, чем их собратья. Скрещиваясь, они будут передавать потомкам часть своего генотипа. Некоторые дети совместят в себе части цепи ДНК, отвечающие за наиболее удачные качества родителей, и, таким образом, окажутся еще более приспособленными.

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

Изредка происходит мутация: некоторый случайный нуклеотид цепи ДНК особи может измениться на другой. Если полученная цепь будет использоваться для создания потомства, то возможно появление у детей совершенно новых качеств.

Естественный отбор, скрещивание и мутация обеспечивают развитие популяции. Каждое новое поколение в среднем более приспособлено, чем предыдущее, т. е. оно лучше удовлетворяет требованиям внешней среды. Этот процесс называется эволюцией.

 Рассматривая эволюцию в природе, возникает мысль о том, что можно искусственно отбирать особи, подходящие нам по некоторым параметрам, создавая таким образом искусственные внешние условия. Это называется селекцией и используется людьми для получения новых пород животных, к примеру, дающих больше молока или с более густой шерстью. Но почему бы не устроить собственную эволюцию с помощью компьютера? Действительно, пусть есть функция, которая по заданному набору численных параметров возвращает некоторое значение (многопараметрическая функция). Создадим множество строк, каждая из которых будет кодировать вектор чисел (длина вектора равна количеству параметров функции). По заданному вектору можно высчитать соответствующее ему значение функции. Те строки, для которых это значение велико, будем считать более приспособленными, чем те, для которых оно мало. Запуская эволюцию на строках по подобию природной, на каждом поколении будем получать строки со все большими значениями функции. Таким образом, такого рода эволюция решает задачу максимизации многопараметрической функции.