|
|
|
содержание .. 27 28 29 30 ..
%
!#*%!#&
F
*:,$* $I*:+*
F
*)&* :&)#*’! +($*,#)KH (*L*)&M
5
@!"!
4
Q
D./.0-1
-.48++
,D4
L04,-+
.
В
теории
сложности
выделяют
массовые
и
индивидуальные
за
-
дачи
.
Первые
из
них
сформулированы
в
общем
виде
,
вторые
представлены
с
конкретными
числовы
-
ми
значениями
исходных
данных
.
Исследования
сложности
проводятся
в
отношении
массовых
задач
и
получаемые
выводы
,
как
правило
,
относятся
к
наихудшему
случаю
—
к
наиболее
неблагоприятно
-
му
возможному
сочетанию
исходных
данных
.
Цель
исследований
—
установление
вида
зависимости
объема
Q
требуемых
вычислений
от
раз
-
мера
задачи
N
.
Объем
вычислений
может
определяться
числом
арифметических
и
логических
опера
-
ций
или
затратами
процессорного
времени
ЭВМ
с
заданной
производительностью
.
Размер
задачи
в
общем
случае
связывают
с
объемом
описания
задачи
,
но
в
приложениях
понятие
размера
легко
напол
-
няется
более
конкретным
содержанием
.
Далее
,
в
теории
сложности
задач
выбора
вводят
понятие
эффективных
и
неэффективных
алго
-
ритмов
.
К
э
EE$%&’(*./
относят
алгоритмы
с
полиномиальной
зависимостью
Q
от
N
,
например
,
ал
-
горитмы
с
функцией
Q
(
N
)
линейной
,
квадратичной
,
кубической
и
др
.
Для
*$BEE$%&’(*.,
алгоритмов
характерна
экспоненциальная
зависимость
Q
(
N
).
Важность
проведения
резкой
границы
между
полиномиальными
и
экспоненциальными
алгорит
-
мами
вытекает
из
сопоставления
числовых
примеров
роста
допустимого
размера
задачи
с
увеличени
-
ем
быстродействия
Б
используемых
ЭВМ
(
табл
. 4.
1
,
в
которой
указаны
размеры
задач
,
решаемых
за
одно
и
то
же
время
?
на
ЭВМ
с
быстродействием
Б
i
при
различных
зависимостях
сложности
Q
от
раз
-
мера
N
).
Эти
примеры
показывают
,
что
выбирая
ЭВМ
в
O
раз
более
быстродействующую
,
получаем
увеличение
размера
решаемых
задач
при
линейных
алгоритмах
в
O
раз
,
при
квадратичных
алгорит
-
мах
в
К
1
/2
раз
и
т
.
д
.
Иначе
обстоит
дело
с
неэффективными
алгоритмами
.
Так
,
в
случае
сложности
2
N
для
одного
и
того
же
процессорного
времени
раз
-
мер
задачи
увеличивается
только
на
lg
K
/ lg2
единиц
.
Следовательно
,
переходя
от
ЭВМ
с
Б
=
1
Gflops
к
суперЭВМ
с
Б
=
1
Tflops,
мож
-
но
увеличить
размер
решаемой
задачи
только
на
1
0,
что
совершенно
недостаточно
для
прак
-
тических
задач
.
Действительно
,
в
таких
зада
-
чах
,
как
например
,
синтез
тестов
для
БИС
число
входных
двоичных
переменных
может
составлять
бо
-
лее
1
50
и
поэтому
полный
перебор
всех
возможных
проверяющих
кодов
потребует
выполнения
более
2
1
50
вариантов
моделирования
схемы
.
В
теории
сложности
все
комбинаторные
задачи
разделены
на
классы
:
—
класс
неразрешимых
задач
,
в
который
входят
массовые
задачи
,
решение
которых
полным
пе
-
ребором
принципиально
невозможно
с
точки
зрения
современных
научных
представлений
;
этот
класс
отделяется
от
других
задач
так
называемым
пределом
Бреммермана
,
оцениваемым
величиной
N
=
1
0
93
;
отметим
,
что
реальный
предел
неразрешимости
значительно
ниже
;
—
класс
P
,
к
которому
относятся
задачи
,
для
которых
известны
алгоритмы
решения
полиноми
-
альной
сложности
;
—
класс
NP
,
включающий
задачи
,
для
которых
можно
за
полиномиальное
время
проверить
пра
-
вильность
решения
,
т
.
е
.
ответить
на
вопрос
,
удовлетворяет
ли
данное
решение
заданным
условиям
;
очевидно
,
что
P
включено
в
NP
,
однако
вопрос
о
совпадении
этих
классов
пока
остается
открытым
,
хотя
по
-
видимому
на
этот
вопрос
будет
получен
отрицательный
ответ
;
—
класс
NP
-
полных
задач
,
характеризующийся
следующими
свойствами
:
1
)
для
этих
задач
не
-
известны
полиномиальные
алгоритмы
точного
решения
; 2)
любые
задачи
внутри
этого
класса
могут
быть
сведены
одна
к
другой
за
полиномиальное
время
.
Последнее
означает
,
что
если
будет
найден
по
-
линомиальный
алгоритм
для
точного
решения
хотя
бы
одной
NP
-
полной
задачи
,
то
за
полиномиаль
-
ное
время
можно
будет
решить
любую
задачу
этого
класса
.
Из
результатов
теории
сложности
следуют
важные
практические
рекомендации
:
1
)
приступая
к
решению
некоторой
комбинаторной
задачи
,
следует
сначала
проверить
,
не
принадлежит
ли
она
к
&
.
+
.
)
"#$%!#&’&($"!))$* +($*,#&($"!)&*
115
Q
(
N
)
Б
1
Б
2
=
1
00
Б
1
Б
3
=
1
000
Б
1
N
N
1
1
00
N
1
1
000
N
1
N
2
N
2
1
0
N
2
3
1
.6
N
2
N
3
N
3
4.64
N
3
1
0
N
3
2
N
N
4
6.64+
N
4
9.97+
N
4
M:BD+=:
4.
)
%
!#*%!#&
F
*:,$* $I*:+*
F
*)&* :&)#*’! +($*,#)KH (*L*)&M
5
@!"!
4
классу
NP
-
полных
задач
,
и
если
это
так
,
то
не
следует
тратить
усилия
на
разработку
алгоритмов
и
про
-
грамм
точного
решения
; 2)
отсутствие
эффективных
алгоритмов
точного
решения
массовой
задачи
выбора
отнюдь
не
означает
невозможности
эффективного
решения
индивидуальных
задач
из
класса
NP
-
полных
или
невозможности
получения
приближенного
решения
по
эвристическим
алгоритмам
за
полиномиальное
время
.
Q9
4
D;=+4001.
/.-
4
51
.
F(#4<=’#**.$
/$&#-.
(
ЭМ
)
предназначены
для
поиска
предпочти
-
тельных
решений
и
основаны
на
статистическом
подходе
к
исследованию
ситуаций
и
итерационном
приближении
к
искомому
состоянию
систем
.
В
отличие
от
точных
методов
математического
программирования
ЭМ
позволяют
находить
ре
-
шения
,
близкие
к
оптимальным
,
за
приемлемое
время
,
а
в
отличие
от
известных
эвристических
мето
-
дов
оптимизации
характеризуются
существенно
меньшей
зависимостью
от
особенностей
приложения
(
т
.
е
.
более
универсальны
)
и
в
большинстве
случаев
обеспечивают
лучшую
степень
приближения
к
оп
-
тимальному
решению
.
Универсальность
ЭМ
определяется
также
применимостью
к
задачам
с
немет
-
ризуемым
пространством
управляемых
переменных
(
т
.
е
.
среди
управляемых
переменных
могут
быть
и
лингвистические
).
Важнейшим
частным
случаем
ЭМ
являются
8$*$&’1$+%’$
/$&#-.
’
)48#"’&/.
.
Генетические
алгоритмы
(
ГА
)
основаны
на
поиске
лучших
решений
с
помощью
наследования
и
усиления
полезных
свойств
множества
объектов
определенного
приложения
в
процессе
имитации
их
эволюции
.
Свойства
объектов
представлены
значениями
параметров
,
объединяемыми
в
запись
,
называе
-
мую
в
ЭМ
,"#/#+#/#;
.
В
ГА
оперируют
хромосомами
,
относящимися
к
множеству
объектов
—
0#07
-
49=’’
.
Имитация
генетических
принципов
—
вероятностный
выбор
родителей
среди
членов
популя
-
ции
,
скрещивание
их
хромосом
,
отбор
потомков
для
включения
в
новые
поколения
объектов
на
осно
-
ве
оценки
целевой
функции
—
ведет
к
эволюционному
улучшению
значений
целевой
функции
(
функ
-
ции
полезности
)
от
поколения
к
поколению
.
Среди
ЭМ
находят
применение
также
методы
,
которые
в
отличие
от
ГА
оперируют
не
множест
-
вом
хромосом
,
а
единственной
хромосомой
.
Так
,
метод
дискретного
4#%)45*#8#
0#’+%)
(
его
англо
-
язычное
название
Hillclimbing
)
основан
на
случайном
изменении
отдельных
параметров
(
т
.
е
.
значений
полей
в
записи
или
,
другими
словами
,
значений
генов
в
хромосоме
).
Такие
изменения
называют
/7
-
&)=’9/’
.
После
очередной
мутации
оценивают
значение
E7*%=’’
0#4$6*#+&’
F
(Fitness Function)
и
результат
мутации
сохраняется
в
хромосоме
только
,
если
F
улучшилась
.
В
другом
ЭМ
под
названием
“
L#-$4’"#()*’$
#&@’8)
” (Simulated Annealing)
результат
мутации
сохраняется
с
некоторой
вероят
-
ностью
,
зависящей
от
полученного
значения
F
.
"4,-
:04
97
:
?:5:
A+
34+,7
:
43-+/
:
DF016
8.I.0+2
,
34
/
4RF;
@
.0.-+A.
,7+6
:
D@
48+-/
4
9
.
Для
применения
ГА
необходимо
:
1
)
выделить
совокупность
свойств
объекта
,
характеризуемых
внутренними
параметрами
и
вли
-
яющих
на
его
полезность
,
т
.
е
.
выделить
множество
управляемых
параметров
X
= (
x
1
,
x
2
,...
x
n
);
среди
x
i
могут
быть
величины
различных
типов
(real, integer, Boolean, enumeration).
Наличие
нечисловых
ве
-
личин
(enumeration)
обусловливает
возможность
решения
задач
не
только
параметрической
,
но
и
структурной
оптимизации
;
2)
сформулировать
количественную
оценку
полезности
вариантов
объекта
—
функцию
полезно
-
сти
F
.
Если
в
исходном
виде
задача
многокритериальна
,
то
такая
формулировка
означает
выбор
ска
-
лярного
(
обобщенного
)
критерия
;
3)
Разработать
математическую
модель
объекта
,
представляющую
собой
алгоритм
вычисления
F
для
заданного
вектора
N
;
4)
Представить
вектор
N
в
форме
хромосомы
—
записи
следующего
вида
В
ГА
используется
следующая
терминология
:
8$*
—
управляемый
параметр
x
i
;
)44$45
—
значение
гена
;
P
1
P
2
P
3
. . . .
P
n
&
.
+
.
)
"#$%!#&’&($"!))$* +($*,#&($"!)&*
116
%
!#*%!#&
F
*:,$* $I*:+*
F
*)&* :&)#*’! +($*,#)KH (*L*)&M
5
@!"!
4
4#%7+
(
0#6’=’9
)
—
позиция
,
занимаемая
геном
в
хромосоме
;
8$*#&’0
—
экземпляр
хромосомы
,
генотип
представляет
совокупность
внутренних
параметров
проектируемого
с
помощью
ГА
объекта
;
8$*#E#*-
—
множество
всех
возможных
генотипов
;
E7*%=’9
0#4$6*#+&’
(
приспособленности
)
F
—
целевая
функция
;
E$*#&’0
—
совокупность
генотипа
и
соответствующего
значения
F
,
под
фенотипом
часто
пони
-
мают
совокупность
выходных
параметров
синтезируемого
с
помощью
ГА
объекта
.
"84,-
42
@
.0.-+A.
,7+2
:
D@
48+-/
.
Вычислительный
процесс
начинается
с
генерации
исходно
-
го
поколения
—
множества
,
включающего
N
хромосом
,
N
—
размер
популяции
.
Генерация
выполня
|