МИНИСТЕРСТВО  ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

УО «БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ ТРАНСПОРТА»

 

ФАКУЛЬТЕТ «МЕХАНИЧЕСКИЙ» 

КАФЕДРА «ЭЛЕКТРИЧЕСКИЙ ПОДВИЖНОЙ СОСТАВ»

 
 
 

КУРСОВАЯ  РАБОТА 

по дисциплине

«Математическое моделирование» 
 

«Использование генетических алгоритмов для поиска решения задач ГЭТ» 
 
 
 
 
 

Выполнил:        Проверил:

студент группы МГ-31      преподаватель

Соболь П.С.       Олешкевич Н.А. 

Гомель, 2011

 

Изм.

Лист

№ докум.

Подпись

Дата

Лист

2

КР.МГ-31.14.2011

  Разраб.

Соболь  П.С.

  Провер.

Олешкевич Н.А. 

  Реценз. 

  Н. Контр. 

  Утверд. 

Использование генетических алгоритмов для поиска решения задач по ГЭТ

Лит.

Листов

33

     БелГУТ

     

     Содержание.

Введение………………………………………………………………………...…3

История появления эволюционных алгоритмов……………………….……….5

Решение задачи в формульном виде……………………………………….…...19

Решение задачи в числовом виде………………………………………….……25

Заключение……………………………………………………………………….32

Список литературы………………………………………………………………33 

 

Изм.

Лист

№ докум.

Подпись

Дата

Лист

3

КР.МГ-31.14.2011 

Введение. 

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

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

    Персональная  ЭВМ давно превратилась в предмет  труда. Ни одно предприятие не обходится  без электронной базы данных, без  современных средств коммуникаций, мощных вычислительных средств. Он позволяет  осуществлять не только производственный процесс на дому, но и целый ряд  всевозможных процессов.

    Огромный  вклад в этот рост внесло развитие технологии математического моделирование.

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

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

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

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

Изм.

Лист

№ докум.

Подпись

Дата

Лист

4

КР.МГ-31.14.2011 

В курсовой работе я исследую математическую модель  генетического алгоритма.

    Генетический  алгоритм (от англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

      В работе предстоит высчитать выживаемость (fitness) потомства с помощью математической модели генетического алгоритма. Найти более приспособленное к жизни потомство.

 

Изм.

Лист

№ докум.

Подпись

Дата

Лист

5

КР.МГ-31.14.2011 

История появления эволюционных алгоритмов

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

     Теория  эволюции повлияла на изменение мировоззрения  людей с самого своего появления. Теория, которую Чарльз Дарвин представил в работе, известной как "Происхождение  Видов", в 1859 году, стала началом  этого изменения. Многие области  научного знания в настоящее время  наслаждаются свободой мысли в атмосфере, которая многим обязана революции, вызванной теорией эволюции и  развития. Но Дарвин, подобно многим своим современникам, кто предполагал, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Его гипотеза о пангенезисе оказалась  неправильной. Это было на пятьдесят  лет до того, как теория наследственности начала распространяться по миру, и  за тридцать лет до того, как "эволюционный синтез" укрепил связь между  теорией эволюции и относительно молодой наукой генетикой. Однако Дарвин выявил главный механизм развития: отбор в сочетании с изменчивостью  или, как он его называл, "спуск  с модификацией". Во многих случаях, специфические особенности развития через изменчивость и отбор все  еще не бесспорны, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемых в Природе.

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

Изм.

Лист

№ докум.

Подпись

Дата

Лист

6

КР.МГ-31.14.2011 

История эволюционных вычислений началась с разработки ряда различных независимых моделей. Основными из них были генетические алгоритмы и классификационные  системы Голланда (Holland), опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги, ставшей классикой в этой области, - "Адаптация в естественных и искусственных системах" ("Adaptation in Natural and Artifical Systems", 1975). В 70-х годах в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идей бионического поведения особей. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию. Развивая идеи Цетлина М.Л. о целесообразном и оптимальном поведении стохастических автоматов, Неймарк Ю.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел (Fogel) и Уолш (Walsh). Несмотря на разницу в подходах, каждая из этих "школ" взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере.

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

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

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

     2) Системы, которые являются биологически более реалистичными, но которые не оказались особенно полезными в прикладном смысле.

Изм.

Лист

№ докум.

Подпись

Дата

Лист

7

КР.МГ-31.14.2011 

Они больше похожи на биологические системы и менее  направлены (или не направлены вовсе). Они обладают сложным и интересным поведением, и, видимо, вскоре получат практическое применение.

     Конечно, на практике мы не можем разделять  эти вещи так строго. Эти категории - просто два полюса, между которыми лежат различные вычислительные системы. Ближе к первому полюсу - эволюционные алгоритмы, такие как  Эволюционное Программирование (Evolutionary Programming), Генетические Алгоритмы (Genetic Algorithms) и Эволюционные Стратегии (Evolution Strategies). Ближе ко второму полюсу - системы, которые могут быть классифицированы как Искусственная Жизнь (Artificial Life).

     Конечно, эволюция биологических систем не единственный "источник вдохновения" создателей новых методов, моделирующих природные  процессы. Нейронные сети (neural networks), например, основаны на моделировании поведения нейронов в мозге. Они могут использоваться для ряда задач классификации, например, задачи распознавания образов, машинного обучения, обработки изображений и др. Область их приложения частично перекрывается со сферой применения ГА. Моделируемый отжиг (simulated annealing) - другая методика поиска, которая основана скорее на физических, а не биологических процессах.