К вопросу о тестировании генетических алгоритмов

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Курейчик В.М., Лебедев П.К., Лях А.В. Проблемы эволюционной адаптации в САПР, Новинтех. 1991. №3.

2. Куре йчик В.М. Методы геиети ческого поиска. Учебное пособие, Часть 1, Таганрог: Изд-во ТРТУ, 1998. 118с.

3. http://www.math.nsc.ru/AP/benchmarks/UFLP/uflp_ga.html _

4. http://www. algolist. manual.ru

5. Holland J.H. Adaptation in Natural and Artificial Systems. An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. University of Michigan, 1975, 210p.

УДК 658.512

СИ. Родзин

К ВОПРОСУ О ТЕСТИРОВАНИИ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ

Круг задач решаемых с использованием генетических алгоритмов (ГА) постоянно расширяется, ГА адаптируются к реальному эволюционному процессу, создаются новые разновидности генетических операторов, к ним добавляются ламар-ковские операторы [1]. Развитие методов компьютерной поддержки принятия решений требует дальнейшего совершенствования и исследования ГА [2,3]. Одним из направлений исследований в этой области является тестирование ГА.

Эффективность ГА при решении конкретной задачи принято оценивать двумя факторами: скоростью (время достижения заданного качества популяции или ее ) (

из точки локального экстремума и способность постоянно увеличивать качество

).

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

,

, .

,

имеется в Лондонском Королевском Колледже [4]. В библиотеке рАРЫБ [5] собраны тестовые примеры и функции для классических задач квадратичного про.

- -

ния перестановок. В частности, пусть задано множество N={1, 2,...,п}. Если у -некоторая перестановка на множестве N то требуется максимизировать функцию :

¥,-¥ j

1- j

= 2 • , i, j = 1,2,..., n.

1=1 ¡=+1 j-1

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

n 10 20 30 40 50 60 70 80 90 100

Fmax(V) 163.9 833.4 2111.5 4051.7 6693.3 10064.7 14189.8 19094.2 24791.0 31301.5

Другими известными тестовыми задачами являются задачи минимизации нелинейных несепарабельных функций Розенбрука, Гриванка и Шеффера [6]:

Рк (хх, х2) = 100(х12 - х2)2 + (1 - хх)2, хх,х2 е [- 2.048;2.047],

n x2

Fg (x,, xxn ) = 1 + У !-------------------П

12 у 4000 if

x

cos(-£- ) VI

, x, e [- 512;51l],

J

sin2 J x2 + x2 - 0.5 2 2 r 1

FSi(x,,x2) = 0.5 + t------------------------F,x:,x2 e [-100;100],

,1.0 + 0.001 • (xf + x 2)]

Fs2(x1,x2) = (xf + x2)025 •[sin2(50• (xf + x2)01) +1.0}x1,x2 e [-100;100]

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Курейчик В.В. Эволюционные, синергетические и гомеостатические методы принятия решений. Таганрог: Изд-во ТРТУ, 2001.

2. Ковалев С.М., Родзин С.И. Информационные технологии: интеллектуализация обучения, моделирование эволюции, распознавание речи. Ростов-на-Дону: Изд-во СКНЦ ВШ, 2002.

3. Родзин С.И. Гибридные интеллектуальные системы на основе алгоритмов эволюционного программирования // Новости искусственного интеллекта. 2000. №3. С.159-170.

4. http: // www.mscmga.ms.ic.ac.uk/info.html

5. http: //fmatbhp1.tu-graz.ac.at/%7Ekarisch/qaplib/

6. Whitley D. et al. Building Better Test Functions // Proc. of 6th Int. Conf. on GA, San Francisco, 1995.

УДК 681.3:536.2.072

О.Б. Лебедев, АЛ. Дуккардт АЛГОРИТМ БЕССЕТОЧНОЙ ТРАССИРОВКИ СОЕДИНЕНИЙ РАЗНОЙ ШИРИНЫ

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

( ) .