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

Оглавление

Введение

Глава 1. Применение теоретико-вероятностных методов к анализу генетических алгоритмов

1.1. Генетические алгоритмы и их основные характеристики

1.2. Математический анализ некоторых схем репродукции

1.2.1. Пропорциональная репродукция

1.2.2. Турнирная репродукция

1.2.3. Репродукция с линейным упорядочиванием

1.3. Оператор скрещивания и его разновидности

1.3.1. Некоторые "традиционные" операторы скрещивания

1.3.2. Операторы скрещивания в задачах с подстановками

1.4. Оператор мутации

1.5. Вопросы применимости генетических методов для решения задач прикладной математики

Выводы

Глава 2. Разработка генетических алгоритмов решения систем булевых уравнений

2.1. Постановка задачи решения систем булевых уравнений

2.2. Общая схема поиска с обучением и ее применение для метода генетического поиска

2.2.1. Анализ существующих алгоритмов обучения

2.2.1.1. Схема выбора оператора скрещивания

2.2.1.2. Схема выбора оператора репродукции

2.2.2. Схема локального поиска

2.2.3. Общая схема самообучающегося генетического алгоритма

2.3. Совместное применение генетических алгоритмов и метода разделяющих плоскостей для решения систем булевых уравнений

Выводы

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

3.1. План проведения экспериментальных исследований

3.1.1 Оценка точности полученных характеристик и необходимого числа испытаний

3.1.2. Построение, оценка адекватности и точности аналитических моделей

3.2. Системы булевых уравнений с пороговыми функциями

3.3. Системы булевых уравнений рекуррентного типа 132 Выводы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные положения, выносимые на защиту, заключаются в следующем.

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

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

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

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

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

Апробация работы. Основные результаты работы докладывались на второй межведомственной конференции "Научно-техническое и информационное обеспечение деятельности спецслужб" (г. Москва, 1998 г.); третьей межведомственной конференции "Научно-техническое и информационное обеспечение деятельности спецслужб" (г. Москва, 2000 г.); VII Всероссийской конференции "Нейрокомпьютеры и их применение" (14-16 февраля 2001 г., г. Москва); XXVI международной конференции "Информационные технологии в науке, образовании, телекоммуникации и бизнесе" - IT+SE'99 (20-30 мая 1999 г. Гурзуф-Ялта); XXVII международной конференции "Информационные технологии в науке, образовании, телекоммуникации и бизнесе" - IT+SE'2000 (17-27 мая 2000 г. Гурзуф-Ялта); семинарах, проводимых на кафедре "Криптография" в Институте криптографии, связи и информатики и на кафедре "САПР" Московского государственного технического университета им. Н.Э. Баумана.

Публикации. По теме диссертации опубликовано 8 печатных работ, в том числе: 3 статьи, 5 тезисов докладов.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы, приложений. Диссертация содержит 154 страницы, 13 таблиц, 14 рисунков и 3 приложения. Список использованных источников включает 122 наименования.

Основные результаты диссертационного исследования заключаются в следующем.

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

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

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

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

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

6. Разработана методика оценки эффективности алгоритма решения систем булевых уравнений. Численные оценки эффективности позволили сравнить на основе эмпирических данных по ряду показателей разработанные ГА с другими известными алгоритмами переборного типа. Решение отдельных классов систем булевых уравнений показало, что предложенные алгоритмы эффективнее таких алгоритмов, как алгоритм Балаша, алгоритм случайного спуска и метод тотального опробования, обычно используемых при решении рассматриваемых задач.

141

Направления дальнейших исследований.

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

До сих пор не получены теоретические обоснования сходимости ГА.

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

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

ЗАКЛЮЧЕНИЕ.

1. Айала Ф. Введение в популярную и эволюционную генетику - М.: Мир, 1984.

2. Алиханян и др. Общая генетика. М., 1985.

3. Анри-Лабордер А., Кофман А. Методы и модели исследования операций. -М.: Мир, 1977.-432 с.

4. Балакин Г.В. Введение в теорию случайных систем уравнений: Труды по дискретной математике / Под редакцией В.Н. Сачкова и др.- М.: ТВП, 1997.-Т. 1.-С. 1-18.

5. Балакин Г.В., Никонов В.Г. Методы сведения булевых уравнений к системам пороговых соотношений // Обозрение прикладной и промышленной математики 1994 - Т. 1, вып. 3 - С. 389-401.

6. Балакин Г.В. Эффективно решаемые классы систем булевых уравнений // Обозрение прикладной и промышленной математики- 1995 Т. 2, вып. 3- С. 494-501.

7. Балаш Э. Аддитивный алгоритм для решения задач линейного программирования с переменными, принимающими значения 0 и 1 // Кибернетический сб.- 1969.- Вып. 6.- С. 217-252.

8. Батищев Д.И. , Булгаков И.В., Власов С.Е. Решение задачи "слепого" упорядочения при помощи генетических алгоритмов // Обозрение прикладной и промышленной математики- 1996- Т. 3, вып. 5. С. 725-734.

9. Батищев Д.И. Генетические алгоритмы решения экстремальных задач. -Воронеж, 1995.

10. Батищев Д.И., Коган Д.И. Вычислительная сложность экстремальных задач переборного типа Нижний Новгород, 1994.

11. Белоусов Е.Г. Введение в выпуклый анализ и целочисленное программирование М.: изд-во МГУ, 1977.- 342 с.

12. Букатова И.JI. и др. Эвоинформатика. Теория и практика эволюционного моделирования М.: Наука, 1991.

13. Букатова И.Л. Эволюционное моделирование и его приложения. -М.: Наука, 1979.

14. Бусленко Н.П., Шрейдер Ю.А. Метод статистических испытаний М., 1961.-228 с.

15. Бутаков Е.А. Методы синтеза релейных устройств из пороговых элементов. -М.: Энергия, 1970.

16. Буш Р., Мостеллер Ф. Стохастические модели обучаемости. -М.: Физматгиз, 1962.

17. Ведерникова О.Г. Разработка и исследование комбинированного алгоритма генетического поиска и имитации отжига для задачи размещения элементов СБИС. Диссертация на соискание ученой степени кандидата технических наук Ростов на Дону, 1999 - 150 с.

18. Вентцель Е.С. Исследование операций М.: Сов. радио, 1972 - 552 с.

19. Воеводин В.В. Математические модели и методы в параллельных процессах-М.: Наука, 1986.-296 с.

20. Волконский В.А., Левина Л.В., Поманский А.М., Пятецкий-Шапиро И.И. Об одном итерационном методе решения задач целочисленного программирования // Докл. Акад. Наук СССР- 1966- Т. 169, № 6. -С. 1289-1292.

21. Горшков С.П. Применение теории NP-полных задач для оценки сложности решения систем булевых уравнений // Обозрение прикладной и промышленной математики 1995 - Т. 2, вып. 3 - С. 325-398.

22. Гришухин В.П. Среднее число итераций в алгоритме Балаша // Численные методы в линейном программировании М.: Наука, 1973- С. 31-38.

23. Денисов Д.В. Методы покоординатного спуска в задачах условной минимизации // Журн. выч. матем. и матем. физики 1978 - Т. 18 - № 5. -С. 1103-1111.

24. Дертоузос М. Пороговая логика М.: Мир, 1967.

25. Дудников Е.Е., Рыбашов М.В. Градиентные методы решения линейных неравенств и задач линейного программирования на ЭВМ- М.: Сов. радио, 1970 194 с.

26. Еремеев A.B. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации. Диссертация на соискание ученой степени кандидата физико-математических наук.- Омск, 2000. 119 с.

27. Зуев Ю.А., Иванов С.К. Обучение и самообучение в процедурах взвешенного голосования // Ж. вычисл. мат. и мат. физ 1995 - Т. 35. -№ 1.-С. 104-121.

28. Зуев Ю.А. Пороговые функции и пороговые представления булевых функций // Матем. вопросы кибернетики 1994- Вып. 5 - С. 5-61.

29. Кисляков A.B. Генетические алгоритмы: математический анализ некоторых схем репродукции // Информационные технологии- 2000. -№ 12.-С. 9-14.

30. Кисляков A.B. Генетические алгоритмы: операторы скрещивания и мутации // Информационные технологии 2001- № 1.- С. 29-34.

31. Кисляков А.В., Никонов В.Г. Самообучающийся генетический алгоритм решения систем булевых уравнений // Научный вестник МГТУ ГА. Серия "информатика".- 2001.-№ 38.- С. 28-33.

32. Кисляков А.В. Применение генетических алгоритмов для решения систем уравнений с искажениями // Материалы Третьей межведомственной конференции "Научно-техническое и информационное обеспечение деятельности спецслужб".- М.: ИКСИ, 2000.- Т. 2.- С. 124-125.

33. Коллингвуд Э., Корн Д., Росс П. О трудностях предсказания успешности применения генетических алгоритмов // Обозрение прикладной и промышленной математики-1996 -Т. 3, вып. 5 С. 626-636.

34. Корбут А.А., Финкелынтейн Ю.Ю. Дискретное программирование М.: Наука, 1969.- 368 с.

35. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров-М., 1968 -720 с.

36. Косачевский О.Т., Норенков И.П. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации // Информационные технологии 1999 - № 2- С. 2-7.

37. Курейчик В.М. Генетические алгоритмы в проектировании СБИС. Учебное пособие-Таганрог: Издательство ТРТУ, 1997.- 106 с.

38. Курейчик В.М. Методы генетического поиска. Учебное пособие. -Таганрог, 1998.

39. Линейное и нелинейное программирование / Ляшенко И.И., Карагодова Е.А., Черникова Н.В., Шор Н.З.- Киев: Вища школа, 1975 384 с.

40. Маккалок У.С., Питтс У. Логическое исчисление идей, относящихся к нервной активности// Автоматы-М.: ИЛ, 1956 -С. 362-384.

41. Никонов В.Г. Классификация минимальных базисных представлений всех булевых функций от четырех переменных // Обозрение прикладной и промышленной математики 1994 - Т. 1, вып. 3 - С. 458-545.

42. Никонов В.Г. Пороговые представления булевых функций // Обозрение прикладной и промышленной математики- 1994- Т. 1, вып. 3. С. 402-457.

43. Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации // Информационные технологии 1999. - № 1. -С. 2-7.

44. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность-М.: Мир, 1985.-510 с.

45. Петров Д.Ф. Генетика с основами селекции М.: Высшая школа, 1971. -410с.

46. Плукене Д.Б. Решение линейных псевдобулевых уравнений и неравенств // Сб. "Вопросы синтеза логики ЦВМ".- 1974.- Т. 1.- С. 62-70.

47. Прюгель-Беннетт А., Рэттрэй М., Шапиро Дж. Применение методов статистической механики для изучения динамики генетического алгоритма // Обозрение прикладной и промышленной математики 1996. -Т. 3, вып. 5.-С. 670-687.

48. Растригин J1.A. Метод случайного поиска в задачах многопараметрической оптимизации // Автоматика и вычислительная техника-Рига, 1963.

49. Растригин JI.A., Рипа К.К. Непрерывный алгоритм самообучения при многопараметрической оптимизации методом случайного поиска // Автоматика и вычислительная техника Рига, 1965.

50. Растригин J1.A. Случайный поиск в задачах оптимизации многопараметрических систем-Рига: Зинатне, 1965.

51. Растригин JI.A. Статистические методы поиска М.: Наука, 1968.

52. Рябец М.Н. Разработка и исследование генетических алгоритмов компоновки по критериям числа внешних связей и задержки распространения сигналов. Диссертация на соискание ученой степени кандидата технических наук Таганрог, 2000 - 140 с.

53. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации.

54. Скурихин А.Н. Разработка и применение самоадаптирующихся генетических алгоритмов. Диссертация на соискание ученой степени кандидата физико-математических наук Пущино, 1996 - 147 с.

55. Смирнов В.Г. Системы булевых уравнений рекуррентного типа // Обозрение прикладной и промышленной математики.- 1995 Т. 2, вып. 3.-С. 477-482.

56. СхрейверА. Теория линейного и целочисленного программирования-М.: Мир, 1991.

57. Taxa X. Введение в исследование операций М.: Мир, 1985 - Т. 1.- 479 с.

58. Теория и применение случайного поиска / А.Т. Бахарев, А.К. Зуев, М.М. Камилов и др.; Под ред. Л. А. Растригина- Рига: Зинатне, 1969- 307 с.

59. Трубин В.А. О методе решения задач целочисленного линейного программирования специального вида // Докл. Акад. Наук СССР 1969. -Т. 189.-№5.-С. 552-554.

60. Уоссермен Ф. Нейрокомпьютерная техника М.: Мир, 1992.

61. Усачев Е.С. О предельных распределениях в стохастической модели обучаемости // Докл. Акад. Наук СССР.- 1964.- Т. 159.- № 6.

62. Файзуллин А.З. Разработка и исследование генетических методов размещения двумерных геометрических объектов. Диссертация на соискание ученой степени кандидата физико-математических наук. -Таганрог, 1996 161 с.

63. Финкелынтейн Ю.Ю. Алгоритм для решения задач целочисленного программирования с булевыми переменными // Экономика и математические методы 1965-№ 5 - С. 745-759.

64. Финкелынтейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования-М.: Наука, 1976.-264 с.

65. Хачиян Л.Г. Полиномиальный алгоритм в линейном программировании // Докл. Акад. Наук СССР.- М, 1979.- Т. 244, № 5.- С. 1093-1096.

66. Хачиян Л.Г. Сложность задач линейного программирования // Математика и кибернетика М.: Наука, 1987- Вып. 10 - 48 с.

67. Черников С.Н. Линейные неравенства М.: Наука, 1968 - 488 с.

68. Шаффер Дж. Д., Эшельман Л. Дж. Комбинаторная оптимизация с использованием генетических алгоритмов: важность отличия генотипа от фенотипа // Обозрение прикладной и промышленной математики 1996. -Т. 3, вып. 5.-С. 656-669.

69. Щеглов С.Н. Разработка и исследование генетических методов расслоения топологии СБИС. Диссертация на соискание ученой степени кандидата технических наук Таганрог, 1998 - 141 с.

70. Экономико-математические методы и прикладные модели: Учеб. пособие для вузов / В.В. Федосеев, А.Н. Гармаш, Д.М. Дайитбегов и др.; Под ред. В.В. Федосеева.-М.: ЮНИТИ, 1999.-391 с.

71. Atkinson R.C., Estes W.K. Stimulus sampling theory In: R.D. Luce, R.R. Bush and E. Galanter // Handbook of mathematical psychology - N.Y.- № 21963.

72. Atkinson R.C., Suppes P. Markov learning models for multiperson interactions. -Stanford, 1960.

73. Bäck Т., Hoffmeister F., Schwefel H.-P. Applications of evolutionary algorithms. Systems Analysis Research Group. Technical Report SYS-2/92, University of Dortmund, 1992.

74. Bäck T. Selective pressure in evolutionary algorithms: A characterization of selection mechanisms // Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence (ICEC94), 1994.-P. 57-62.

75. Biethahn J., Nissen V. Evolutionary algorithms in management applications.-Berlin: Springer, 1995.

76. Blickle Т., Thiele L. A comparison of selection schemes used in genetic algorithms. TIK-Report, № 11,1995.

77. Blickle T., Thiele L. A mathematical analysis of tournament selection. In L.J. Eshelman, editor // Proceedings of the Sixth International Conference on Genetic Algorithms, 1995-P. 9-16.

78. Burke C.J., Estes W.K. A theory of stimulus variability in learning // Psychol. Rev., 1950.-№57.

79. Caruana R., Eschelman L., Schaffer D. Biases in the crossover landscape // Proceedings of the Third International Conference on Genetic Algorithms.- Morgan Kaufmann Publishing, 1989.- P. 10-19.

80. Darwin C. The origin of species. John Murray, London, 1859.

81. Davis L. Adapting operator probabilities in genetic algorithms // Proceedings of the Third International Conference on Genetic Algorithms- La Jolla: Morgan Kaufmann Publishers, 1989.-P. 60-69.

82. Deb K., Goldberg D. E. A comparative analysis of selection schemes used in genetic algorithms. In G. Rawlins, editor, Foundations of Genetic Algorithms.- San Mateo CA: Morgan Kaufmann Publishers, 1991- P. 69-93.

83. De Jong K. A. An analysis of the behavior of a class of genetic adaptive systems, Doctoral thesis, Dept. Computer and Communication Sciences, University of Michigan, Ann Arbor, 1975.

84. De Jong K. A., Spears W. An analysis of the interacting roles of population size and crossover in genetic algorithms // Proceedings of the First International Conference on parallel problem solving from nature Dortmund, Germany, October 1990.-P. 38-47.

85. Dexter T. W., Goodman E. D., Punch W. F., III. Local optimization in two-dimensional layout problems. Technical report. Case center for computer-aided engineering and manufacturing- East Lansing: Michigan State University, 1996.

86. Estes W. K. Towards a statistical theory of learning // Psychol. Rev., 1950. № 57.

87. Fogarty T. C. Varying the probability of mutation in the genetic algorithm. In J. D. Schaffer, editor // Proceedings of the Third International Conference on Genetic Algorithms- San Mateo CA: Morgan Kaufmann Publishers, 1989. -P. 104-109.

88. Fogel D.B., Saravanan N. Bibliography of evolutionary computation and applications. Department of Mechanical Engineering. Technical Report FAU-ME-93-100, Florida Atlantic University, 1993.

89. Forrest S., Jones T. C. Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In L.J. Eshelman, editor // Proceedings of the Sixth International Conference on Genetic Algorithms, 1995.

90. Forrest S., Mitchell M. What makes a problem hard for a genetic algorithm? Some anomalous results and their explanation // Machine Learning- 1992. -№13.- P. 285-319.

91. Goldberg D., Lingle R. Alleles, loci, and the traveling salesman problem // Proceedings of the First International Conference on Genetic Algorithms and their application Pittsburgh: Lawrence Erlbaum Associates, 1985 - P. 141153.

92. Goodman E. D. Introduction to GALOPPS the Genetic Algorithm Optimized for Portability and Parallelism. Technical report. Case center for computer-aided engineering and manufacturing- East Lansing: Michigan State University, 1995.

93. Goodman E. D., Punch W. F., Wang G. Simultaneous multi-level evolution. GARAGe technical report Department of computer science, Michigan state university, 1996.

94. Goodman E. D. The extended SGA / island parallel GA system. Technical report. Case center for computer-aided engineering and manufacturing. East Lansing: Michigan State University, 1994.

95. Grefenstette J. J. Optimization of control parameters for genetic algorithms. IEEE Transactions on systems, man and cybernetics- Vol. SMC-16, №1, 1986.-P. 122-128.

96. Holland J. H. Adaptation in natural and artificial systems The University of Michigan Press, Ann Arbor, MI, 1975.

97. Ivanescu P.L., Rudeanu S. Pseudo-boolean methods for bivalent-programming-Lect. Notes. Math.- 1966, V. 23.

98. Janssen M., Kepner M., Nelson B., Spillman R. Use of genetic algorithm in the cryptanalysis of simple substitution ciphers // Cryptologia- 1993- Vol. 17, №1.-P. 31-44.

99. Josifescu M., Theodorescu R. On Bush-Mosteller stochastic models learning // J. Math. Psychol.-Vol. 2, № 1.- 1965.

100. Josifescu M., Theodorescu R. Some remarks on certain models for learning // Rev. Math. Pures appl.- № 7 1962.

101. Kadaba N., Nygard K. E. Improving the performance of genetic algorithm in automated discovery of parameters. Draft. Dept. of SC and OR, North Dakota State Univ., January 25, 1990.

102. Karlin S. Some random walks arising in learning models 1 // Pac. J. Math. -№ 3 1953.

103. Macready W. G., Wolpert D. H. What makes an optimization problem hard? Technical report 95-05-046, Santa Fe Institute, 1995.

104. Muhlenbein H. How genetic algorithms really work: I. Mutation and hillclimbing. In Manner and Manderick, 1992 P. 15-25.

105. Muhlenbein H., Schliercamp-Voosen D. Predictive models for the breeder genetic algorithm. Evolutionary Computation 1993- V. 1- №1- P. 25-49.

106. Muroga S. Threshold logic and its applications New York, 1971 - 478 p.

107. Reiter S., Sherman G. Discrete optimizing // J. Soc. Industr. Appl. Math. 1965-V. 13.-№3.-P. 864-889.

108. Restle F. A survey and classification of learning models In: R. R. Bush, W. K. Estes. Studies in mathematical learning theory - Stanford, 1959.

109. Spears W. M. The role of mutation and recombination in evolutionary algorithms. Philosophy Doctoral thesis, George Mason University, Fairfax, Virginia, 1998.

110. Syswerda G. Schedule optimization using genetic algorithms. In: Handbook of genetic algorithms. / Ed. By L. Davis. New York: Van Nostrand Reinhold, 1991.-P. 332-349.

111. Syswerda G. Uniform crossover in genetic algorithms // Proceedings of the Third International Conference on Genetic Algorithms Morgan Kaufmann Publishing, 1989.-P. 2-9.

112. Theodorescu R. New interpretation of certain stochastic models for learning // Rend. Accad. Naz. Lincei.- V. 8.- № 28.- 1960.