Xreferat.com » Рефераты по информатике и программированию » Реализация генетических алгоритмов нейрокомпьютерами

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

Введение

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

Нейрокомпьютерные исследования в России

Генетические алгоритмы

Реализация генетических алгоритмов

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

Символьная модель простого генетического алгоритма

Работа простого генетического алгоритма

Шима (schema)

Теорема шим

Перспективные направления развития нейрокомпьютерных технологий

Заключение

Литература

Введение


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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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


Нейрокомпьютерные исследования в России


Нейрокомпьютинг, как новое направление науки, ведет свою историю с середины 40-х, когда Маккаллок и Питтс опубликовали свою работу "Логическое исчисление идей, относящихся к нервной активности", в которой изложили принципы функционирования искусственного нейрона. Дальнейшие исследования в 50-х - 60-х годах в мире и в нашей стране подогрели интерес к этой новой области науки. Выход в свет фундаментальных работ Минского, в которых он теоретически доказал, что отдельные нейронные парадигмы не способны решать некоторые задачи, в частности, с помощью однослойного персептрона нельзя решить задачу "исключающего или", фактически затормозил развитие нейрокомпьютинга, практический интерес к нейронным сетям быстро угас и переместился в теоретическую плоскость.

Такое положение сохранялось почти три десятка лет, до середины 80-х. Конец 80-х - начало 90-х характеризуются сначала робким, а потом бурным возрождением интереса к нейронным сетям во всем мире. В России его массовый всплеск проявится позднее - лет через пять, в середине 90-х. А в мире события развиваются достаточно бурно. Резко увеличивается число конференций по нейронной тематике, регулярно проводятся конференции IEEE, посвященные исключительно нейронным сетям, секции по нейронной тематике начинают появляться в различных симпозиумах, посвященных обработке сигналов, робототехнике, авионике и т.д. Лавинообразно нарастает объем литературы, выпускаются сначала десятки, а потом сотни книг по нейронным сетям. А в России - тишина, лишь отдельные коллективы либо продолжают заниматься исследованиями в области нейрокомпьютинга, как делали это уже много лет, либо, отследив всплеск интереса, начинают заниматься этой тематикой. Но уже к 1992 году таких коллективов было не так уж и мало.

Разумеется, перечислить всех, кто в то время занимался нейрокомпьютингом невозможно, поскольку, помимо представленных известных имен, существовало множество небольших научных коллективов и групп, работающих в этой области. Дело в том, что нейрокомпьютерные исследования в России проводились разрозненно, отдельные коллективы не знали про разработки коллег из других городов, что, несомненно, шло во вред развитию нейрокомпьютинга в России. Скажем, профессор Горбань из Красноярска был в свое время весьма удивлен тем, что в Москве серьезно занимаются нейрокомпьютерными исследованиями. Ответное удивление последовало и со стороны столичных разработчиков. И такие случаи не были редкостью.

К 1992 году было создано Российское общество по нейронным сетям (RNNS) - по аналогии со Всемирным обществом по нейронным сетям (WNNS). Под его эгидой в октябре 1992 года в Ростове-на-Дону прошла первая Международная конференция по нейроинформатике и нейрокомпьютингу. Участниками той конференции стали такие гранды нейрокомпьютинга, как Роберт Хехт-Нильсен, глава компании HNC, занимающейся выпуском нейрокомпьютеров, Роберт Маркс, координатор IEEE по нейронным сетям, Дональд Вюнш, представлявший корпорацию Boeing и др. Общение с ними оказалось весьма полезным для российских участников конференции.

Годом раньше на базе Омского Государственного Университета была проведена Всероссийская студенческая олимпиада по нейрокомпьютингу. К сожалению, первая олимпиада оказалась и последней. А жаль, ведь сейчас во многих отечественных вузах читаются курсы по нейрокомпьютингу, причем преподавание ведется разными научными школами, и было бы весьма интересно провести очередную всероссийскую олимпиаду, которая была бы полезна всем. К сожалению, пока это остается мечтой. Начиная с 1993 года, в Красноярске ежегодно проводится конференция по нейрокомпьютингу, доклады на которую присылаются со всей страны. Она фактически стала первой регулярной российской конференцией по нейронным сетям. В МИФИ стали ежегодно проводить школу-семинар "Нейроинформатика", переросшую впоследствии во всероссийскую конференцию. Прошли также несколько специализированных семинаров по нейронной тематике (как, например, совместный российско-британский семинар "Нейроинформатика-90"). Нельзя сказать, что в России совсем уж не уделяли внимания нейронным сетям, но исследований проводилось мало.

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


Генетические алгоритмы


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

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

Идею генетических алгоритмов высказал Дж. Холланд в конце шестидесятых - начале семидесятых годов XX века. Он заинтересовался свойствами процессов естественной эволюции (в том числе фактом, что эволюционируют хромосомы, а не сами живые существа). Холланд был уверен в возможности составить и реализовать в виде компьютерной программы алгоритм, который будет решать сложные задачи так, как это делает природа - путем эволюции. Поэтому он начал трудиться над алгоритмами, оперировавшими последовательностями двоичных цифр (единиц и нулей), получившими название хромосом. Эти алгоритмы имитировали эволюционные процессы в поколениях таких хромосом. В них были реализованы механизмы селекции и репродукции, аналогичные применяемым при естественной эволюции. Так же, как и в природе, генетические алгоритмы осуществляли поиск "хороших" хромосом без использования какой-либо информации о характере решаемой задачи. Требовалась только некая оценка каждой хромосомы, отражающая ее приспособленность. Механизм селекции заключается в выборе хромосом с наивысшей оценкой (т.е. наиболее приспособленных), которые репродуцируют чаще, чем особи с более низкой оценкой (хуже приспособленные). Репродукция означает создание новых хромосом в результате рекомбинации генов родительских хромосом. Рекомбинация - это процесс, в результате которого возникают новые комбинации генов. Для этого используются две операции: скрещивание, позволяющее создать две совершенно новые хромосомы потомков путем комбинирования генетического материала пары родителей, а также мутация, которая может вызывать изменения в отдельных хромосомах.

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

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

Генетические Алгоритмы - адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Они основаны на генетических процессах биологических организмов: биологические популяции развиваются в течении нескольких поколений, подчиняясь законам естественного отбора и по принципу "выживает наиболее приспособленный" открытому Чарльзом Дарвином. Подражая этому процессу генетические алгоритмы способны "развивать" решения реальных задач, если те соответствующим образом закодированы. Например, генетические алгоритмы могут использоваться, чтобы проектировать структуры моста, для поиска максимального отношения прочности/веса, или определять наименее расточительное размещение для нарезки форм из ткани. Они могут также использоваться для интерактивного управления процессом, например на химическом заводе, или балансировании загрузки на многопроцессорном компьютере. Вполне реальный пример: израильская компания Schema разработала программный продукт Channeling для оптимизации работы сотовой связи путем выбора оптимальной частоты, на которой будет вестись разговор. В основе этого программного продукта и используются генетические алгоритмы.

Основные принципы генетических алгоритмов были сформулированы Голландом (Holland, 1975), и хорошо описаны во многих работах. В отличии от эволюции, происходящей в природе, генетический алгоритм только моделируют те процессы в популяциях, которые являются существенными для развития. Точный ответ на вопрос: какие биологические процессы существенны для развития, и какие нет? - все еще открыт для исследователей.


Реализация генетических алгоритмов


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

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

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

Имеются много способов реализации идеи биологической эволюции в рамках генетического алгоритма. Традиционным считается генетический алгоритм, представленный на схеме 1:


НАЧАЛО /генетический алгоритм/


Создать начальную популяцию

Оценить приспособленность каждой особи

останов := FALSE

ПОКА НЕ останов ВЫПОЛНЯТЬ

НАЧАЛО /создать популяцию нового поколения/

ПОВТОРИТЬ (размер_популяции/2) РАЗ

НАЧАЛО /* цикл воспроизводства */

Выбрать две особи с высокой приспособленностью из предыдущего поколения для скрещивания.

Скрестить выбранные особи и получить двухпотомков

Оценить приспособленности потомков

Поместить потомков в новое поколение

КОНЕЦ

ЕСЛИ популяция сошлась ТО останов := TRUE

КОНЕЦ

КОНЕЦ


Схема 1. Реализация генетического алгоритма


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

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


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


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

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

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

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

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


Символьная модель простого генетического алгоритма


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

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: