|
|
|
содержание .. 28 29 30 31 ..
%
!#*%!#&
F
*:,$* $I*:+*
F
*)&* :&)#*’! +($*,#)KH (*L*)&M
5
@!"!
4
щиеся
аллели
1
, 2
и
9
последовательно
заменяются
на
значения
3, 5
и
4.
L7&)=’’
.
Бывают
точечными
(
в
одном
гене
),
макромутациями
(
в
нескольких
генах
)
и
хромосом
-
ными
(
появление
новой
хромосомы
).
Обычно
вероятность
появления
мутации
указывается
среди
ис
-
ходных
данных
.
Но
возможно
автоматическое
регулирование
числа
мутаций
при
их
реализации
толь
-
ко
в
ситуациях
,
когда
родительские
хромосомы
различаются
не
более
чем
в
K
генах
.
:$4$%=’9
.
После
определения
и
положительной
оценки
потомка
он
может
быть
сразу
же
вклю
-
чен
в
текущую
популяцию
вместо
худшего
из
своих
родителей
,
при
этом
из
алгоритма
исключается
внешний
цикл
(
что
однако
не
означает
сокращения
общего
объема
вычислений
).
Другой
вариант
селекции
—
отбор
после
каждой
операции
скрещивания
двух
лучших
экземпля
-
ров
среди
двух
потомков
и
двух
родителей
.
Часто
член
популяции
с
минимальным
(
лучшим
)
значением
целевой
функции
принудительно
включается
в
новое
поколение
,
что
гарантирует
наследование
приобретенных
этим
членом
положи
-
тельных
свойств
.
Такой
подход
называют
B4’&’6/#/
.
Обычно
элитизм
способствует
более
быстрой
сходимости
к
локальному
экстремуму
,
однако
в
многоэкстремальной
ситуации
ограничивает
возмож
-
ности
попадания
в
окрестности
других
локальных
экстремумов
.
+-0B.
F690.
.
Хромосому
N
*
будем
называть
точкой
локального
минимума
,
если
F
(
X
*)<
F
(
X
i
)
для
всех
хромо
-
сом
X
i
,
отличающихся
от
X
*
значением
единственного
гена
,
где
F
(
X
) —
значение
функции
полезности
в
точке
N
.
Следующий
вариант
селекции
—
отбор
N
экземпляров
среди
членов
репродукционной
группы
,
которая
составляется
из
родителей
,
потомков
и
мутантов
,
удовлетворяющих
условию
F
i
<
t
,
где
t
—
пороговое
значение
функции
полезности
.
Порог
может
быть
равен
или
среднему
значению
F
в
теку
-
щем
поколении
,
или
значению
F
особи
,
занимающей
определенное
порядковое
место
.
При
этом
мяг
-
кая
схема
отбора
—
в
новое
поколение
включаются
N
лучших
представителей
репродукционной
груп
-
пы
.
Жесткая
схема
отбора
—
в
новое
поколение
экземпляры
включаются
с
вероятностью
q
i
:
N
r
q
i
= (
F
max
-
F
i
) /
∑
(
F
max
-
F
j
)
j=
W
где
N
r
—
размер
репродукционной
группы
.
!$"$70#"9-#1$*’$
.
Кроме
перечисленных
основных
операторов
,
находят
применение
некоторые
дополнительные
.
К
их
числу
относится
оператор
переупорядочения
генов
—
изменения
их
распреде
-
ления
по
локусам
.
Назначение
переупорядочения связано
со
свойством
,
носящим
название
эпистасис
.
F0’+&)+’+
имеет
место
,
если
функция
полезности
зависит
не
только
от
значений
генов
(
аллелей
),
но
и
от
их
по
-
зиционирования
.
Наличие
эпистасиса
говорит
о
нелинейности
целевой
функции
и
существенно
ус
-
ложняет
решение
задач
.
Действительно
,
если
некоторые
аллели
двух
генов
оказывают
определенное
положительное
влияние
на
целевую
функцию
,
образуя
некоторую
связку
(
схему
),
но
вследствие
эпи
-
стасиса
при
разрыве
связки
эти
аллели
оказывают
уже
противоположное
влияние
на
функцию
полез
-
ности
,
то
разрывать
такие
схемы
не
следует
.
А
это
означает
,
что
связанные
эпистасисом
гены
жела
-
тельно
располагать
близко
друг
к
другу
,
т
.
е
.
при
небольших
длинах
схем
.
Оператор
переупорядочения
помогает
автоматически
“
нащупать
”
такие
совокупности
генов
(
они
называются
хромосомными
бло
-
ками
или
building blocks)
и
разместить
их
в
близких
локусах
.
K
.0.-+A.
,7+2
/.-
4
5
7
4
/B+0+84
9:0+>
T98+,-+7
.
Возможны
два
подхода
к
формированию
хромосом
.
Первый
из
них
основан
на
использовании
в
качестве
генов
проектных
параметров
.
Например
,
в
задаче
размещения
микросхем
на
плате
локусы
соответствуют
посадочным
местам
на
плате
,
а
генами
являются
номера
(
имена
)
микросхем
.
Другими
словами
,
значением
k
-
го
гена
будет
номер
микросхемы
в
k
-
й
позиции
.
Во
втором
подходе
генами
являются
не
сами
проектные
параметры
,
а
номера
эвристик
,
исполь
-
зуемых
для
определения
проектных
параметров
.
Так
,
для
задачи
размещения
можно
применять
не
-
сколько
эвристик
.
По
одной
из
них
в
очередное
посадочное
место
нужно
помещать
микросхему
,
име
-
ющую
наибольшее
число
связей
с
уже
размещенными
микросхемами
,
по
другой
—
микросхему
с
ми
-
нимальным
числом
связей
с
еще
не
размещенными
микросхемами
и
т
.
д
.
Генетический
поиск
в
этом
&
.
+
.
)
"#$%!#&’&($"!))$* +($*,#&($"!)&*
119
%
!#*%!#&
F
*:,$* $I*:+*
F
*)&* :&)#*’! +($*,#)KH (*L*)&M
5
@!"!
4
случае
есть
поиск
последовательности
эвристик
,
обеспечивающей
оптимальный
вариант
размещения
.
Второй
подход
получил
название
—
/$&#-
%#/2’*’"#()*’9
B("’+&’%
.
Этот
метод
оказывается
предпочтительным
во
многих
случаях
.
Например
,
в
задачах
синтеза
расписаний
распределяется
за
-
данное
множество
работ
во
времени
и
между
обслуживающими
устройствами
—
серверами
,
т
.
е
.
про
-
ектными
параметрами
для
каждой
работы
будут
номер
сервера
и
порядковый
номер
в
очереди
на
об
-
служивание
.
Пусть
N
—
число
работ
,
M
—
число
серверов
.
Если
гены
соответствуют
номерам
работ
,
то
в
первом
подходе
в
хромосоме
нужно
иметь
2
N
генов
и
общее
число
отличающихся
друг
от
друга
хромосом
W
заметно
превышает
наибольшее
из
чисел
N
!
и
M
N
.
Согласно
методу
комбинирования
эвристик
,
число
генов
в
хромосоме
в
два
раза
меньше
,
чем
в
первом
подходе
,
и
равно
N.
Поэтому
если
число
используемых
эвристик
равно
K
,
то
мощность
мно
-
жества
возможных
хромосом
уже
несравнимо
меньше
,
а
именно
W = K
N
.
Очевидно
,
что
меньший
размер
хромосомы
ведет
к
лучшей
вычислительной
эффективности
,
а
меньшее
значение
W
позволяет
быстрее
найти
окрестности
искомого
экстремума
.
Кроме
того
,
в
мето
-
де
комбинирования
эвристик
все
хромосомы
,
генерируемые
при
кроссовере
,
будут
допустимыми
.
В
то
же
время
при
применении
обычных
генетических
методов
необходимо
использовать
процедуры
ти
-
па
PMX
для
корректировки
генов
,
относящихся
к
номерам
в
очереди
на
обслуживание
,
что
также
сни
-
жает
эффективность
поиска
.
P38:L0.0+>
+
94384,1
5D>
,:/4740-84D>
1
.
Дайте
формулировку
задачи
математического
программи
-
рования
.
2.
В
чем
заключаются
трудности
решения
многокритериаль
-
ных
задач
оптимизации
?
3.
Что
такое
“
множество
Парето
”?
4.
Для
функции
,
заданной
своими
линиями
равного
уровня
(
рис
. 4.
1
4),
постройте
траектории
поиска
методами
конфигураций
,
деформируемого
многогранника
,
наискорейшего
спуска
из
исход
-
ной
точки
N
0
.
5.
Как
Вы
считаете
,
можно
ли
применять
метод
проекции
градиента
для
решения
задач
оптимизации
с
ограничениями
типа
неравенств
?
6.
Что
такое
“
овражная
целевая
функция
”?
Приведите
при
-
мер
такой
функции
для
двумерного
случая
в
виде
совокупности
линий
равного
уровня
.
7.
Какие
свойства
характеризуют
класс
NP
-
полных
задач
?
8.
Морфологическая
таблица
содержит
8
строк
и
24
столбца
.
Сколько
различных
вариантов
структуры
представляет
данная
таблица
?
9.
Приведите
пример
И
-
ИЛИ
графа
для
некоторого
знакомого
Вам
приложения
.
1
0.
Приведите
примеры
продукций
из
знакомого
Вам
приложения
.
11
.
Дайте
предложения
по
постановке
задачи
компоновки
модулей
в
блоки
для
ее
решения
генетически
-
ми
методами
.
Какова
структура
хромосомы
?
&
.
+
.
)
"#$%!#&’&($"!))$* +($*,#&($"!)&*
120
%+,
. 4.
)
4.
Пример
для
построения
траекторий
поиска
:01=.B9?.
1-./?
0
;-3O-6BB93
-
B.=3/0F.1<0.
<3B;2.<1?
:!+(
5.
)
.
J<07=++
,.-.94@4
384@8://04@4
4B.,3.A.0+>
J<07=++
+
6
:8:7-.8+,-+7+
,
.-.916
43.8:=+40016
,+,-./
.
В
ПО
АС
принято
выделять
об
-
щесистемное
ПО
,
системные
среды
и
прикладное
ПО
.
К
общесистемному
ПО
относят
операционные
системы
(
ОС
)
используемых
ЭВМ
и
вычисли
-
тельных
систем
и
сетевое
ПО
типовых
телекоммуникационных
услуг
.
Различают
ОС
со
встроенными
сетевыми
функциями
и
оболочки
над
локальными
ОС
.
В
соот
-
ветствии
с
другим
признаком
классификации
сетевые
ОС
подразделяют
на
одноранговые
и
функцио
-
нально
несимметричные
(
ОС
для
систем
клиент
-
сервер
).
Основные
функции
сетевой
ОС
:
—
управление
каталогами
и
файлами
;
—
управление
ресурсами
;
—
коммуникационные
функции
;
—
защита
от
несанкционированного
доступа
;
—
обеспечение
отказоустойчивости
;
—
управление
сетью
.
Q0")(4$*’$
%)&)4#8)/’
’
E);4)/’
является
одной
из
первоочередных
функций
сетевой
ОС
,
об
-
служиваемых
специальной
сетевой
файловой
подсистемой
.
Пользователь
получает
от
этой
подсисте
-
мы
возможность
обращаться
к
файлам
,
физически
расположенным
в
сервере
или
в
другой
станции
данных
,
применяя
привычные
для
локальной
работы
языковые
средства
.
Q0")(4$*’$
"$+7"+)/’
включает
в
себя
функции
запроса
и
предоставления
ресурсов
.
O#//7*’%)=’#**.$
E7*%=’’
обеспечивают
адресацию
,
буферизацию
,
маршрутизацию
сообщений
.
Z)A’&)
#&
*$+)*%=’#*’"#()**#8#
-#+&70)
возможна
на
любом
из
следующих
уровней
:
ограни
-
чение
доступа
в
определенное
время
,
и
(
или
)
для
определенных
станций
,
и
(
или
)
заданное
число
раз
;
ограничение
совокупности
доступных
конкретному
пользователю
директорий
;
ограничение
для
кон
-
кретного
пользователя
списка
возможных
действий
(
например
,
только
чтение
файлов
);
пометка
фай
-
лов
символами
типа
“
только
чтение
”, “
скрытность
при
просмотре
списка
файлов
”.
U&%)6#7+&#;1’(#+&5
определяется
наличием
у
серверов
автономных
источников
питания
,
ото
-
бражением
или
дублированием
информации
в
дисковых
накопителях
.
Отображение
заключается
в
хранении
двух
копий
данных
на
двух
дисках
,
подключенных
к
одному
контроллеру
,
а
дублирование
означает
подключение
каждого
из
этих
двух
дисков
к
разным
контроллерам
.
Сетевая
ОС
,
реализую
-
щая
дублирование
дисков
,
обеспечивает
более
высокий
уровень
отказоустойчивости
.
Дальнейшее
по
-
вышение
отказоустойчивости
связано
с
дублированием
серверов
.
Чем
сложнее
сеть
,
тем
острее
встают
вопросы
70")(4$*’9
+$&5<
.
Основные
функции
управле
-
ния
сетью
реализуются
в
ПО
,
поддерживающем
протоколы
управления
такие
,
как
ICMP
и
SNMP
в
стеке
TCP/IP
или
протокол
CMIP (Common Management Information Protocol)
в
семиуровневой
моде
-
ли
ISO.
Как
рассмотрено
выше
,
это
ПО
представлено
менеджерами
|