Эвристические комбинаторные алгоритмы

Содержание

Слайд 2

Алгоритмы: Анализ и Построение

Краткая классификация алгоритмов

Алгоритмы: Анализ и Построение Краткая классификация алгоритмов

Слайд 3

Алгоритмы: Анализ и Построение

Эвристические комбинаторные алгоритмы

Эвристические алгоритмы дают решение хуже оптимального.

Алгоритмы: Анализ и Построение Эвристические комбинаторные алгоритмы Эвристические алгоритмы дают решение хуже

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

Слайд 4

Общая постановка задачи построения расписания

Алгоритмы: Анализ и Построение

Существует множество различных постановок задачи

Общая постановка задачи построения расписания Алгоритмы: Анализ и Построение Существует множество различных
построения расписаний. Здесь рассмотрен простой её вариант (bin packing) в приложении к планированию заданий с учетом требуемых ресурсов.
Пусть заданы m боксов (bin) B1, B2, …, Bm, каждый объёмом c.
Пусть также даны n единиц хранения p1, p2, …, pn,
n>> m, объем каждого pi, 1≤i≤n, обозначим r(pi). Предполагается, что ∀i r(pi)≤c.
Все pi надо так разместить в Bi, чтобы некоторый функционал Φ достиг экстремума (равномерность, минимум не занятого объёма, и т.д.)

Слайд 5

Алгоритмы: Анализ и Построение

Пусть, к примеру, Bi трактуются как процессорные элементы мультикомпьютера,

Алгоритмы: Анализ и Построение Пусть, к примеру, Bi трактуются как процессорные элементы
c – объём имеющихся в каждом Bi ресурсов, pi – процессы, которые должны быть исполнены на мультикомпьютере и запрашивают для своего исполнения некоторое количество ресурсов r(pi).
Конкретные назначениия pi на Bi задают отображение М (расписание). Допускаются отображения, в которых суммарный запрос ресурса в каждом Bi не превышает c.
Тогда имеем постановки задач построения расписания распределения ресурсов мультикомпьютера

Слайд 6

Алгоритмы: Анализ и Построение

Можно сформулировать 3 проблемы:
P1. Для фиксированного c найти минимальное число

Алгоритмы: Анализ и Построение Можно сформулировать 3 проблемы: P1. Для фиксированного c
боксов m, в которые могут быть упакованы все pi.
Это, например, случай планирования загрузки мультикомпьютера с целью так минимизировать число используемых для решения задачи процессоров, чтобы успеть её решить к заданному моменту времени Т.
Здесь функционал качества расписания Ф - это минимум ресурсов, необходимых для решения задачи к моменту Т.

Слайд 7

Алгоритмы: Анализ и Построение

P2. Для фиксированного m найти минимальное c такое, что все

Алгоритмы: Анализ и Построение P2. Для фиксированного m найти минимальное c такое,
pi могут быть упакованы в m боксов.
Это случай, когда надо найти минимальную производительность процессорных элементов мультикомпьютера с m процессорами, достаточную для решения задачи в заданное время.
Здесь производительность процессорных элементов мультикомпьютера играет роль функционала качества Ф

Слайд 8

Алгоритмы: Анализ и Построение

P3. Для фиксированных m и c найти максимальное n'≤n

Алгоритмы: Анализ и Построение P3. Для фиксированных m и c найти максимальное
такое, что n' единиц хранения могут быть упакованы в m боксов.
Это случай, когда имеющийся мультикомпьютер должен быть максимально использован (задача пакетной обработки).
Все три проблемы имеют экспоненциальную сложность и для их решения должны использоваться переборные алгоритмы нахождения приближенного решения.

Слайд 9

Алгоритмы: Анализ и Построение

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

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

Слайд 10

Алгоритмы: Анализ и Построение

Рассмотрим сначала алгоритм построения множества всех допустимых расписаний для

Алгоритмы: Анализ и Построение Рассмотрим сначала алгоритм построения множества всех допустимых расписаний
случая m=n. Каждое расписание представляется n-кой (набором) вида (p1,p2,…,pn), где p1 в первой позиции набора означает назначение процесса p1 на исполнение на процессор B1 и так далее.
Пусть на качество допустимых расписаний не накладываются никакие ограничения,
На каждый процессор назначается только один процесс. В число допустимых расписаний попадает, например, (p1,p1,…,p1).
Тогда все множество допустимых расписаний строится тем же алгоритмом прибавления единицы, каким строятся все n-ричные числа от нуля до nn-1. Число всех допустимых расписаний в данном случае равно nn.

Слайд 11

Алгоритмы: Анализ и Построение

В программировании обычно n>>m. Поэтому надо разрешать назначение на

Алгоритмы: Анализ и Построение В программировании обычно n>>m. Поэтому надо разрешать назначение
один процессор нескольких процессов и тогда множество допустимых расписаний увеличится, так как в каждой позиции набора появится ещё возможность перебора и станут допустимыми расписания типа ({p1,p2}, {p3,p4}, …,{pn-1,pn}). Множества допустимых расписаний, конечно, очень велики и на практике работать с ними нельзя.
Ограничения задачи могут значительно сократить множество допустимых расписаний. Для параллельных программ возможно ограничение, чтобы каждый процесс был назначен не более чем на один процессор, при этом расписания типа (p1,p1,…,p1), ({p1,p2}, {p1,p3},…,{pn-1,pn}) становятся не допустимыми. Ограничение естественное, если не надо обеспечивать высокую надежность вычислений. В противном случае оно недопустимо

Слайд 12

Алгоритмы: Анализ и Построение

Другое ограничение связано с учетом информационных зависимостей. Если она

Алгоритмы: Анализ и Построение Другое ограничение связано с учетом информационных зависимостей. Если
существует, например, между процессами p1 и p2, и процессоры B1 и B2 соседние (связаны физическим линком), а процессоры B1 и B3 не являются соседними, то расписания типа ({p1,p2}, {p3},…,{pn}) и ({p1}, {p2,p3},…,{pn}) допустимы (информационно зависимые процессы назначены на один или соседние процессоры), а расписание ({p1}, {p3}, {p2},…,{pn}) – не допустимо. Такие сокращения множества допустимых расписаний очень полезны для уменьшения затрат на получение решения, так как отбраковка расписания происходит ещё на этапе его конструирования, часть расписаний не строится вообще, и значение функционала не вычисляется.

Слайд 13

Алгоритмы: Анализ и Построение

К сожалению, добавление новых ограничений при попытке сократить множество

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

Слайд 14

Алгоритмы: Анализ и Построение

Такие стратегии используют некоторое дополнительное знание о задаче. Рассмотрим

Алгоритмы: Анализ и Построение Такие стратегии используют некоторое дополнительное знание о задаче.
следующий пример. Пусть заданы m идентичных процессоров B1, B2, …, Bm. Каждый процессор Bi, 1≤i≤ m, имеет оперативную память размером ⏐Bi⏐. Заданы информационно независимые процессы p1, p2, …, pn, здесь pj:(mj,tj), каждый процесс pj, 1≤j≤n, требует для своего исполнения память объемом mj, время исполнения tj. Необходимо построить (субоптимальное) расписание с приемлемым временем исполнения. Несколько процессов могут быть назначены в процессор Bi, если их суммарный запрос памяти не превышает ⏐Bi⏐.

Слайд 15

Алгоритмы: Анализ и Построение

К примеру, расписание
({p1, p2, p3}, { p5,

Алгоритмы: Анализ и Построение К примеру, расписание ({p1, p2, p3}, { p5,
p9}, {pn-5}, …,{pn})
показывает, что назначенные на процессор B1 процессы {p1, p2, p3} будут и исполняться в порядке перечисления, а именно,: сначала исполнится процесс p1, затем, по его завершении, стартует процесс p2, и затем только выполнится p3.

Слайд 16

Алгоритмы: Анализ и Построение

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

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

Слайд 17

Алгоритмы: Анализ и Построение

Потому разумно для построения расписания использовать такую стратегию:
Строятся

Алгоритмы: Анализ и Построение Потому разумно для построения расписания использовать такую стратегию:
два упорядоченных списка процессов:
- L1 - список процессов, упорядоченных по убыванию объёма запрашиваемой памяти
- L2 - список процессов, упорядоченных по убыванию времени исполнения,
Процессы из первой трети списков L1 и L2 (они содержат процессы с самыми большими запросами ресурсов) назначаются на процессоры, более или менее равномерно заполняя память и потребляя время процессоров.
Затем аналогично назначаются процессы из второй, а затем и последней трети списков L1 и L2.

Слайд 18

Алгоритмы: Анализ и Построение

Построенное расписание на практике может быть и очень хорошим

Алгоритмы: Анализ и Построение Построенное расписание на практике может быть и очень
и не очень, но вряд ли оно будет совсем уж плохим.
Определить понятие приемлемое (хорошее) расписание не просто, однако нередко можно построить оценку стратегии и доказать, насколько построенное решение будет отличаться от оптимального, например, например, будет хуже оптимального не более чем на 30%. Решения в пределах этих 30% и могут считаться приемлемыми.

Слайд 19

Алгоритмы: Анализ и Построение

Это практически полезная стратегия, которая позволяет строить приемлемые расписания.

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

Слайд 20

Алгоритмы: Анализ и Построение

Построение расписания работы домостроительного комбината

Алгоритмы: Анализ и Построение Построение расписания работы домостроительного комбината

Слайд 21

Библиотека фрагментов

Библиотека фрагментов

Слайд 22

Библиотека фрагментов

Библиотека фрагментов

Слайд 23

Библиотека фрагментов

Библиотека фрагментов

Слайд 24

Библиотека фрагментов

Библиотека фрагментов

Слайд 25

Библиотека фрагментов

Библиотека фрагментов

Слайд 26

Библиотека фрагментов

Библиотека фрагментов

Слайд 29

Ещё один способ построения эвристического алгоритма и способ сокращения перебора
ДАНО
Множество бригад b1,

Ещё один способ построения эвристического алгоритма и способ сокращения перебора ДАНО Множество
b2, … , br
- Множество домов d1, d2, … , dl
Множество кранов k1, k2, … , kn, n>r
Время работы tij бригады bi на сборке дома dj
РАСПИСАНИЕ - Таблица (bi, dj, ki1, Tij), где Tij – дата назначения бригады bi на сборку дома dj. Годится расписание с минимальным простоем бригад и кранов.
Самый дорогой ресурс – бригада, её простой недопустим
tkij – время перебазирования крана k от дома di к дому dj

Алгоритмы: Анализ и Построение

Слайд 30

Алгоритмы: Анализ и Построение

b2, dj5,T2j5

b1, dj2, k2,T1j2

b1, dj3,k3, T1j3

b1, dj4,k4, T1j4

b1

b3

b2

b1, dj1,k1,T1j1

b2,

Алгоритмы: Анализ и Построение b2, dj5,T2j5 b1, dj2, k2,T1j2 b1, dj3,k3, T1j3
dj8,k8,T2j8

b2, dj7,k7,T2j7

b2, dj6,T2j6

b3, dj9,k9,T3j9

b3, dj13,k13,T3j13

b3, dj12,k12,T3j12

b3, dj11,k11,T3j11

b3, dj10,k10,T3j10

дни

назначения

Слайд 31

Алгоритмы: Анализ и Построение

Одновременно используются разные краны
Время считается в днях.
Дата Tij =

Алгоритмы: Анализ и Построение Одновременно используются разные краны Время считается в днях.
Tij + tij освобождения бригады bi после выполнения работы dj,
Дата освобождения крана Tij + tkij . В разных расписаниях эти даты разное
Оптимальное/субоптимальное расписание обычно не толерантно к невыполнению расписания.
Алгоритм составления расписания должен быть в некоторой мере толерантен к сбоям в реализации расписания
Учитывается готовность площадок и график готовности новых площадок
Все бригады должны работать без простоев

Слайд 32

Алгоритмы: Анализ и Построение

Алгоритм формирования расписания
Очередное назначение.
Начинает строиться, когда появляется хотя

Алгоритмы: Анализ и Построение Алгоритм формирования расписания Очередное назначение. Начинает строиться, когда
бы одна готовая бригада bi, которая включается в назначение, время Ti1j + tkij
Выбирается один из домов dj, площадка которого готова для начала строительства
Выбирается кран ki из числа свободных
Вычисляется время Tij = Ti(j-1) + tij завершения строительства дома bi
Вычисляется время Tij + tkij освобождения крана ki1 и с этого момента он помещается во множество свободных
Если готовых бригад, кранов или домов нет, время начала назначения отодвигается (Tij + tkij увеличивается на время ожидания)

Слайд 33

Алгоритмы: Анализ и Построение

2. Затем делается первое назначение всех бригад.
3. Затем делается

Алгоритмы: Анализ и Построение 2. Затем делается первое назначение всех бригад. 3.
второе назначение для всех бригад. Бригады, которые на предшествующем шаге закончили работу раньше получают бóльшую работу. И так, пока все дома не построены, т.е. построено распределение.
4. Подсчитывается простой бригад и кранов.
5. Перебор. Далее меняется первое назначение и все последующие, вычисляется простой и так перебираются все распределения. Из них выбирается распределение с минимальным простоем. Это и есть оптимальное решение.
6. Фиксация назначения. При большом числе домов, которые надо построить, перебор становится невыполнимым. Для сокращения перебора делается фиксация частичного распределения.

Слайд 34

Алгоритмы: Анализ и Построение

Сокращение перебора, удовлетворение внесистемных требований. Добавление ограничений/требований
Например, потребовать,

Алгоритмы: Анализ и Построение Сокращение перебора, удовлетворение внесистемных требований. Добавление ограничений/требований Например,
чтобы некоторый конкретный дом был построен до 25 ноября.
Некоторый специальный кран (например, для высотного строительства) должен быть свободен к 1 марта.
Дома bi и bj должны начать строиться одновременно.
Краны не должны пересекать реку.
Имя файла: Эвристические-комбинаторные-алгоритмы.pptx
Количество просмотров: 46
Количество скачиваний: 0