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

Введение

Характеристики задачи

Цель работы

Методы исследования$

Структура работы

1. Основные понятия и формальная постановка задачи

1.1. Модель поведения программы

1.2. Расписание

1.3. Аппаратные средства

1.3.1 Множество процессоров

1.3.2. Коммутационная среда

1.4. Оценка времени выполнения расписания

1.5. Формальная постановка задачи структурного синтеза ВС

2. Характеристика задачи и существующие методы решения

2.1. Характеристика задачи структурного синтеза ВС

2.2. Жадные алгоритмы

2.3. Алгоритмы случайного поиска

2.4. Алгоритмы имитации отжига

2.5. Генетические и эволюционные алгоритмы

2.6. Выводы;

3. Коммутационные среды: параметры, функции стоимости и времени передачи данных

3.1. Полносвязная бесконфликтная КС

3.1.1. Функция вычисления времени передачи данных■

3.1.2. Функция стоимости КС

3.2. Шинные архитектуры

3.2.1. Примеры шинных архитектур

3.2.2. Функция вычисления времени передачи данных

3.2.3. Функция стоимости КС

3.3. Локалъносвязные архитектуры

3.3.1. Архитектура «Трехмерный тор»

3.3.2. Архитектура «Гиперкуб»

3.3.2.1. Примеры архитектур

3.4. Выводы

4. Построение генетических алгоритмов для решения задачи структурного синтеза ВС

4.1. Схема работы генетического алгоритгша

4.2. Проблемы применения генетических алгоритмов для решения задачи структурного синтеза ВС

4.3. Кодирование решений

4.3. Алгоритм восстановления порядка выполнения рабочих интервалов на каждом процессоре ^

4.4. Задание начального приближения

4.5. Критерий останова и функция выживаемости

4.6. Операция селекции

4.7. Операции мутации и скрещивания

4.8. Оценка операционной сложности генетического алгоритма

4.9. Экспериментальное исследование генетического алгоритма

4.9.1. Экспериментальное исследование стабильности работы генетического алгоритма

4.9.2. Экспериментальное исследование качества работы генетического алгоритма

4.9.3. Применение генетического алгоритма для синтеза структуры ВС для решения задачи нахождения координат источников сигнала в фазированных антенных решётках

4.9.4. Результаты экспериментального исследования

4.10 Определение области эффективного применения алгоритма

5. Настройка параметров генетического алгоритма

5.1. Проблема настройки параметров генетического алгоритма

5.2. Метод настройки параметров ГА

5.3. Регрессионная модель для определения значений параметров генетического алгоритма

Характеристики задачи

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

Решение задачи построения ВС обычно проводится поэтапно. Этапы (уровни) проектирования выделяются в соответствии с рассматриваемой детализацией аппаратных и программных средств ВС. Можно выделить три типичных уровня проектирования: абстрактный, системный и уровень регистровых передач [1, 2, 3, 4]. На абстрактном уровне рассматривается возможность построения системы с учётом выполнения заданных ограничений на сроки выполнения прикладной программы и аппаратные ресурсы. На системном уровне определяются характеристики основных компонентов структуры ВС. На уровне регистровых передач происходит проектирование системы с использованием конкретной элементной базы для дальнейшей непосредственной реализации системы. На данном этапе часто рассматриваются задачи автоматического проектирования микросхем, трассировки плат и размещения микросхем на плате.

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

Задача синтеза структуры ВС на системном и абстрактном уровнях проектирования рассматривается в двух вариантах постановки:

• минимизируется время выполнения прикладной программы при заданных ограничениях на аппаратные ресурсы;

• минимизируются аппаратные ресурсы при ограничении времени выполнения прикладной программы.

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

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

• число процессоров;

• тип каждого процессора;

• параметры коммутационной среды;

• расписание.

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

Задача синтеза структуры ВС может быть формализована как задача комбинаторной (дискретной) оптимизации с ограничениями [8]. Эта задача обладает следующими особенностями:

• задача является Л/Р-полной [9, 10];

• оптимизируемые параметры являются разнородными: расписание выполнения программы является графом, параметры аппаратных средств ВС -целочисленными и бинарными переменными;

• функция вычисления времени выполнения программы на ВС является вычислимой (задана алгоритмически);

• аргументы и значения функции вычисления времени выполнения программы являются дискретными.

Проведённый анализ возможных методов решения задачи синтеза структуры ВС по критериям применимости метода, качества решений, вычислительной сложности показал возможные преимущества генетических алгоритмов (ГА) по сравнению с другими методами. ГА обладают следующими преимуществами:

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

2. Скорость сходимости ГА, в отличие от алгоритмов имитации отжига и алгоритмов случайного поиска, не зависит от сложности ландшафта целевой функции и размерности пространства решений.

3. Известны примеры успешного применения ГА для решения задач составления расписаний и синтеза структур ВС на различных уровнях проектирования.

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

Цель работы

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

В рамках данной работы ставятся следующие задачи:

• построение генетического алгоритма решения задачи синтеза структуры ВС, позволяющего оптимизировать широкий набор параметров ВС (расписание, количество и типы процессоров, параметры КС), а именно для построения ГА требуется решить следующие проблемы:

1) выбор способа кодирования решений;

2) определение основных операций и способа их применения;

3) определение метода выбора начального приближения;

4) построение функции выживаемости ГА на основе целевой функции и ограничений;

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

• разработка метода настройки параметров ГА на исходные данные и тип решаемой задачи.

Методы исследования

В данной работе предлагается метод решения задачи синтеза структуры ВС с помощью генетических алгоритмов (ГА). Предлагаемый метод обладает следующими особенностями:

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

• количество итераций алгоритма не зависит от количества оптимизируемых параметров и размера графа поведения программ;

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

Структура работы

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

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

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

В четвёртой главе описывается алгоритм, разработанный для решения задачи структурного синтеза ВС [11, 12]. Предлагается метод кодирования решения, позволяющий учитывать различные наборы оптимизируемых параметров и предотвращающий возникновение некорректных решений. В главе рассматривается построение функции выживаемости для ГА на основе целевой функции и ограничений для задачи синтеза структуры ВС, для предлагаемой схемы кодирования определяются генетические операции: скрещивание, мутация, селекция. Также рассматривается три метода задания начального приближения и их влияние на скорость сходимости алгоритма и качество получаемых решений. Приводятся результаты экспериментальных исследований, и методом статистических испытаний доказывается стабильность работы алгоритма при фиксированных параметрах и начальном приближении. Определяются вычислительная сложность и область эффективного применения алгоритма, оценивается качество получаемых решений. Приводятся результаты экспериментального использования ГА для построения структуры ВС реального времени для решения задачи обнаружения угловых координат источников сигналов в фазированных антенных решетках.

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

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

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

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

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

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

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

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

• предложен метод кодирования решений;

• построена функция выживаемости;

• определены основные операции: селекция, скрещивание, мутация;

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

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

3. Для разработанного в данной работе алгоритма предложен метод вычисления значений его параметров по входным данным.

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

Наиболее перспективным представляется развитие предложенных в работе методов по следующим направлениям:

• расширение набора оптимизируемых параметров, например добавление определения объёма и структуры памяти для каждого процессора;

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

Hessel F., Coste P., Nicolescu G., LeMarrec P., Zergainoh N., Jerraya A. A. Communication Synthesis of Multilanguage Specification // Research Report, TIMA Laboratory, ISRN TIMA-RR-00/06-1-FR, ISSN 1292-8062.

Baghdady A., Zergainoh N-E., Cesario W., Roudier Т., Jerraya A. Design Space Exploration for Hardware/Software Codesign of Multiprocessor Architectures // Research Report, TIMA Laboratory, ISRN TIMA-RR-00/02-4-FR, ISSN 1292-8062. Сверхбольше интегральные схемы и современная обработка сигналов // Под ред. Гуна С., Уайтхауза X., Кайлата Т., М.: Радио и связь, 1989 - 472с. Майоров С.А., Новиков Г.И. Принципы организации цифровых машин // Л.: Машиностроение, 1974-432с.

Valderrama С. et al. COSMOS : A Transformational Codesign Tool for Multiprocessor Architectures // Jorgen Staunstrup and Wayne Wolf eds. Hardware and Software Co-design : Principles and Practice, Kluwer, 1997, p. 307-357. Ernst R., Henkel J., Benner Th., Trawny M. The COSYMA Environment for Hardware/Software Cosynthesis // Journal of Microprocessors and Microsystems, Butterworth-Heinemann, 1995.

Ben-Ismail Т., O'Brien K., Jerraya A. A. PAR-TIF: Interactive System-level Partitioning // VLSI Design Vol. 3 №3.4, pp. 333-345, 1995.

Костенко В.А., Смелянский Р.Л., Трекин А.Г. Синтез структур вычислительных систем реального времени с использованием генетических алгоритмов// Программирование, 2000, №5.

Теория расписаний и вычислительные машины // Под ред. Коффмана Э.Г., М.: Наука, 1984.

Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи // М.: Мир, 1982.

Костенко В.А., Смелянский Р.Л., Трекин А.Г. Генетические алгоритмы: синтез структур вычислительных систем // Тезисы докладов Всероссийской научной конференции "Фундаментальные и прикладные аспекты разработки больших распределенных программных комплексов"(сентябрь 1998 г.,г. Новороссийск) М.: Изд-во МГУ, 1998, С.35-41.

Костенко В.А., Трекин А.Г. Генетические алгоритмы решения смешанных задач целочисленной и комбинаторной оптимизации при синтезе архитектур

ВС // Искусственный интеллект (Донецк), 2000, №2, С.90-96. Смелянский Р.Л. Модель функционирования распределенных вычислительных систем // Вестник МГУ, сер. 15, Вычислительная математика и кибернетика. 1990, №3, С.3-21.

Смелянский Р.Л. Об инварианте поведения программ // Вестник МГУ, сер. 15, Вычислительная математика и кибернетика, 1990, №4, С.54-60. Воеводин Вл. В. Теория и практика исследования параллелизма последовательных программ // Программирование, 1992, №3, С.38-54. Калиниченко Д.В., Капитонова А.П., Ющенко Н.В. Методы и средства прогнозирования времени выполнения последовательных программ. // Сб. Методы математического моделирования. М.: ВМиК МГУ, 1997, №2. Балашов В.В., Капитонова А.П., Костенко В.А., Смелянский Р.Л., Ющенко Н.В. Метод и средства оценки времени выполнения оптимизированных программ // Программирование, 1999, №5, С.52-61

Костенко В.А. Задача построения расписания при совместном проектировании аппаратных и программных средств // Программирование, 2002, №3. Трекин А.Г. Построение расписаний при совместном проектировании аппаратных и программных средств неоднородных ВС с помощью генетических алгоритмов // Труды Международной конференции "Параллельные вычисления и задачи управления" (РАСО'2001). Москва, 2-4 октября 2001 г. Институт проблем управления им. В.А.Трапезникова РАН. -М.: Институт проблем управления им. В.А.Трапезникова РАН, 2001, С.206-213. Мину М. Математическое программирование. Теория и алгоритмы // М.: Наука, 1990.

Костенко В.А. Алгоритмы оптимизации, опирающиеся на метод проб и ошибок, в совместном проектировании аппаратных и программных средств ВС // Труды Всероссийской научной конференции «Высокопроизводительные вычисления и их приложения» (30 октября - 2 ноября 2000 г., Черноголовка). -М.: Изд-во МГУ, 2000, С.123-127.

Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование // Новосибирск: Наука, сибирское отделение, 1977.

Костенко В.А. Задачи синтеза архитектур: формализация, особенности и возможности различных методов для их решения // Программные системы и инструменты. Тематический сборник. М.: МГУ, 2000, № 1.

24] Костенко В.А., Романов В.Г., Смелянский Р.Л. Алгоритмы минимизации аппаратных ресурсов ВС // Искусственный интеллект (Донецк), 2000, №2, С.383-388.

26] Костенко В.А. Метод автоматизированного синтеза параллельных программ для вычислительных систем с MIMD архитектурой // Программирование, 1993, №1, С.43-57.

27] Костенко В.А. Автоматизация составления параллельных программ для вычислительных систем с MIMD архитектурой // Кибернетика и системный анализ, 1995, №5, С.170-179.

28] Костенко В.А. Задачи синтеза архитектур: формализация, особенности и возможности различных методов для их решения // Программные системы и инструменты. Тематический сборник. М.: МАКС Пресс, 2000, №1, С.31-41.

29] Батигцев Д.И., Гудман Э.Д., Норенков И.П., Прилуцкий М.Х. Метод комбинирования эвристик для решения комбинаторных задач упорядочивания и распределения ресурсов // Информационные технологии, 1997, №2, С.29-32.

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

31] Растригин Л.А. Статистические методы поиска // М.: Наука, 1968.

32] Kirkpatrick S., Gelatt С., Vecchi М. Optimization by simulated annealing // Science 220(4598), 1983, p.671-680.

33] Szu H., Hartley R. Fast Simulated annealing // Physics Letters, 1987, 1222(3,4).

34] Ingber L. Very fast simulated re-annealing // Mathematical Computer Modeling, vol. 12, 1989, p.967-973.

35] Bonomi E., button J.-L. The N-city traveling salesman problem: Statistical mechanics and the metropolis algorithm // SLAM Rev. 26 (4), 1984, p.551-568.

36] Holland J.N. Adaptation in Natural and Artificial Systems// Ann Arbor, Michigan: Univ. of Michigan Press, 1975.

37] Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs // Third, Revised and Extended Edition, Springer, 1999.

38] Goldberg D.E. Genetic Algorithms in Search Optimization & Machine Learning // Addison Wesley, Reading, 1989.

39] Mataric M., Cliff D. Challenges in Evolving Controllers for Physical Robots // Robotics and autonomous systems, 19(1), p. 67-83, 1996.

40] Genetic Algorithms in Engineering and Computer Science // Editor Periaux J. and

Winter G., John Wiley & Sons Ltd., 1995.

41] Come D., Fabg H.-L., Mellish C. Solving the Modular Exam Scheduling Problem with Genetic Algorithms // DAI Research Paper №622.

42] Bierwirth C., Kopfer H., Mattfeld D.C., Rixen I. Genetic Algorithm based Scheduling in a Dynamic Manufacturing Environment // Proceedings of the IEEE Conf. on Evolutionary Computation, Perth, IEEE Press, 1995, p.439-443.

43] Fang H.-L., Ross P., Corne D. A Promising genetic Algorithm Approach to Job-Shop Scheduling, Rescheduling, and Open-Shop Scheduling Problems // Proceedings of the Fifth International Conference on Genetic Algorithms, S. Forrest (ed.), San Mateo: Morgan Kaufmann, 1993, p.375-382.

44] Daaldr J., Eklund P.W., Ohmori K. High-Level Synthesis Optimization with Genetic Algorithms // Proceedings of the 4th Pacific Rim International Conference on Artificial Intelligence, Cairns (Australia), 26-30 August 1996, p.276-287.

45] Hallberg J., Peng Z. High-level Synthesis under Local Timing Constraints using Genetic Algorithms // Licentiate Thesis №549, Linkoping University, March 1996.

46] Blickle T. Theory of Evolutional Algorithms and Application to System Synthesis // Dissertation for degree of doctor of technical sciences, Swiss Federal Institute of Technology, Zurich, Diss. ETH № 11894, 1996.

47] Интерфейс магистральный последовательный системы электронных модулей // ГОСТ 26765.52 - 87, М.: Государственный комитет СССР по стандартам, 1987.

48] Шнитман В.З., Кузнецов С.Д. Аппаратно-программные платформы корпоративных информационных систем // Центр Информационных Технологий, http://www.citforum.ru/hardware/svk/contents.shtml

49] Yang T.-Y., Stiles G.S. Guaranteed Message Delivery Time on Real-Time Distributed Systems // Communicating Process Architectures 2001, IOS Press, 2001, p.149-166.

50] Magnus J. High Performance Fiber-Optic Interconnection Networks for Real-Time Computing Systems // Thesis for the degree of doctor of philosophy, Department of Computer Engineering Chalmers University of Technology, Goteborg, Sweden, ISBN 91-7197-852-6, 1999.

51] Shoemaker D., Metcalf C., Ward S. NuMesh: A Communication Architecture for Static Routing // International Conference on Parallel and Distributed Processing Techniques and Applications, November 1995.

52] Коваленко В. Система Exemplar SPP2000 // Открытые Системы, 1997, №1, http://www.osp.rU/os/1997/01/.5.htm

53] Шнитман В. Системы Exemplar SPP1200 // Открытые системы, 1995, №6, С.42-47.

54] Крюков В.А. Операционные системы распределенных вычислительных систем /УМ.: МГУ, 1998.

55] Cray Incorporated // http://www.cray.com/products/systems/t3e

56] Dijkstra E. W. A note on two problems in connection with graphs // Numerische Mathematik, 1959.

57] Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ // М: МЦНМО, 1999-960с.

58] Scherson I.D., Youssef A.S. Interconnection Networks for High-Performance Parallel Computers // IEEE Computer Society Press, Los Alamos, California, 1994.

59] A Beginners Guide to the Intel iPSC/860 // Joint Institute for Computational Science, February 22, 1995.

60] iPSC/2 and iPSC/86 User's Guide // Intel Corporation, 1991

61] Кузьминский M. Гиперкубические метаморфозы // Computerworld, 1997, №17-18.

62] n4 Streaming Media System // PN 109786, nCube, November 2000

63] Вентцель E.C. Теория вероятностей // M.: Высшая школа, 1998.

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

65] Heller D. A survey of parallel algorithms in numerical linear algebra // SIAM Rev., 1978, 20(4), p.740-777.

66] Уилкинсон, Райнш. Справочник алгоритмов на языке АЛГОЛ. Линейная алгебра//М.: Машиностроение, 1976.

67] Воеводин В.В. Численные методы алгебры. Теория и алгоритмы // М.: Наука, 1966.

68] Ковалев М.М. Дискретная оптимизация (целочисленное программирование) // Минск: Изд-во Белорус, ун-та, 1977

69] Land А.Н., and Doig A.G. An automatic method of solving discrete programming problems // Econometrica, v28 (1960), p 497-520.

70] Самарский A.A., Тишкин В.Ф., Колдоба A.B., Повещенко Ю.А. Разностные схемы на нерегулярных сетках // Минск, 1996. — 276 с.

71] Костенко В.А. Особенности параллельной численной реализации в реальном масштабе времени методов сверхразрешения // Радиотехника, 1995, №3, С.32-36.

72] Костенко В.А. Крупноблочный параллелизм в задачах обработки сигналов // Программирование, 1997, №2, С.67-75.

73] Калинина В.Н., Панкин В.Ф. Математическая статистика // М.: Высшая школа, 1998.-336с.

74] Костенко В.А. Принципы построения архитектуры вычислительных систем, унифицированных в классе задач цифровой обработки сигналов в реальном масштабе времени, на основе транспьютеров и сигнальных процессоров // Вестник РТА, 1993, №8.

75] Рабинер JL, Гоулд Б. Теория и применения цифровой обработки сигналов // М.: Мир, 1978.-848с.

76] Монзтнго Р.А., Миллер Т.У. Адаптивные антенные решётки // М.: Радио и связь, 1986.-448с.

77] Уиндроу Б., Стринз С. Адаптивная обработка сигналов. - М.: Радио и связь, 1989.-440с.

78] Отчёт по научно исследовательской работе по теме: «Исследование возможностей использования микропроцессорной высокопроизводительной системы для решения задач разрешения сигналов» // № 01.87.0092 798 гос. per., Таганрог, 1987.

79] Куньсянь JL, Франц Дж. А., Саймар-мл. Р. Цифровые процессоры обработки сигналов // ТИИЭР, т.75, 1987, №8.

80] Michael D., Vose. A. Critical Examination of The Schema Theorem // Technical Report, Department of Computer Science University of Tennessee, November 1993.

81] Altenberg L. The Schema Theorem and Price's Theorem // Whitley, L. D. and Vose, M. D., editors, Foundations of Genetic Algorithms 3, 1995, pp. 23-49, Estes Park, Colorado, USA. Morgan Kaufmarm.

82] Chung, S. W. and Perez R. A. The schema theorem considered insufficient // Proceedings of the Sixth IEEE International Conference on Tools with Articial Intelligence, 1994, p. 748-751, New Orleans.

83] Poli R. Recursive Conditional Schema Theorem, Convergence and Population Sizing in Genetic Algorithms // Proceedings of the Foundation of Genetic Algorithm (FOGA) Workshop, Charlottesville, Virginia, USA, July 2000.

84] Radcliffe N.J. The Algebra of Genetic Algorithms // Technical Report EPCC-TR-92

11, The University of Edinburgh, 1992.

85] Hofmann R. Examinations on the Algebra of Genetic Algorithms // Diploma Thesis, Technical University of Munich, Department of Computer Science, 1993.

86] Golberg D.E., Deb K., Clark J.N. Genetic Algorithms, noise, and the sizing of population // Complex Systems, №6, 1992, p.333-362.

87] Bulmer M.G. Mathematical Theory of Quantitative Genetics // Cambridge: Claredon Press, 1980.

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

89] Vose M.D., Liepins G.E. Punctuated equilibria in genetic search // Complex Systems, №5, 1991, p.31-44.

90] Nix A., Vose M.D. Modeling Genetic Algorithms With Markov Chains // Annals of Mathematics and Artificial Intelligence, 1992, №5, p. 79-88.

91] De Jong K.A., Spears W.M., Gordon D.F. Using Markov Chains to Analyze GAFOs // Proceedings of the Third Workshop on Foundations of Genetic Algorithms (L. Darrell Whitley and Michael D. Vose, Eds.), Morgan Kaufmann, San Francisco, 1995, pp.115-138.

92] Алгоритмы и программы восстановления зависимостей // Под ред. Вапника В.Н., М.: Наука, 1984.-816с.

93] Levenberg К. A method for the solution of certain problems in least squares // Quart. Appl. Math., 2, 1944, p. 164-168.

94] Marquardt D. An algorithm for least-squares estimation of nonlinear parameters // SIAM J. Appl. Math., 21, 1963, p. 431-441.

95] More J. The Levenberg-Marquardt algorithm: implementation and theory // Watson, G.A., ed., Numerical Analysis, Lecture Notes in Mathematics 630, Springer-Verlag, Heidelberg, 1977, p. 105-116.

Заключение