Род Стивенс

Книги → Delphi. Готовые алгоритмы → Глава 8. Деревья решений

Метод Fixed2 (Фиксированный 2) производит всего одно испытание. Он вы­бирает случайное решение и пробует улучшить его в 10 * N раз, случайно заменяя два элемента.

Эвристика NoChangesl (Без изменений 1) выполняет испытания до тех пор, пока в N последовательных испытаниях не будет улучшения. В течение каждого, программа выбирает случайное решение и затем пробует улучшить его, случайно заменяя один элемент до тех пор, пока в течение N последовательных изменений не будет никаких улучшений.

Эвристика NoChanges2 (Без изменений 2) выполняет одно испытание. При этом программа выбирает случайное решение и пытается улучшить его, произ­вольным образом удаляя по две позиции до тех пор, пока в течение N последова­тельных изменений не будет никаких улучшений.

 

Метод отжига

Метод отжига (simulated annealing) заимствован из термодинамики. При от­жиге металл нагревается до высокой температуры. Молекулы в горячем металле совершают быстрые колебания. Если металл медленно охлаждать, то молекулы начинают выстраиваться в линии, образуя кристаллы. При этом молекулы посте­пенно переходят в состояние с минимальной энергией.

Когда металл остывает, соседние кристаллы сливаются друг с другом. Молеку­лы одного кристалла временно покидают свои позиции с минимальной энергией и соединяются с молекулами другого кристалла. Энергия получившегося кристал­ла большего размера будет меньше, чем сумма энергий двух исходных кристаллов. Если металл охлаждать достаточно медленно, кристаллы станут просто огромны­ми. Конечное расположение молекул имеет очень низкую суммарную энергию, по­этому металл становится очень прочным.

Начиная с состояния с высокой энергией, молекулы в конечном счете достига­ют состояния с низкой энергией. На пути к окончательному положению они про­ходят через множество локальных минимумов энергии. Каждая комбинация кри­сталлов представляет локальный минимум. Довести кристалл до минимального энергетического состояния можно только временным разрушением структуры меньших кристаллов, увеличивая тем самым энергию системы, в результате чего кристаллы могут объединиться.

Метод отжига использует аналогичный способ для поиска лучшего решения за­дачи. Когда программа ищет путь решения, она может «застрять» в локальном оп­тимуме. Чтобы избежать этого, она время от времени вносит в решение случайные изменения, даже если очередной вариант и не приводит к мгновенному улучше­нию результата. Это позволит программе выйти из локального оптимума и отыс­кать лучшее решение. Если изменение не приводит к лучшему решению, она обя­зательно отменит это изменение.

Чтобы программа не зациклилась на этих модификациях, алгоритм через ка­кое-то время изменяет вероятность внесения случайных изменений. Вероятность внесения одного изменения равна Р = 1 / Ехр(Е / (к * Т)), где Е - количество «энергии», добавленной к системе, к - константа, выбранная в зависимости от рода задачи и Т - переменная, соответствующая «температуре».

← предыдущая следующая →

Страницы раздела: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Публикация компанией Dropbox кода Zulip – средства общения для IT-разработчиков

20.11.2015
Одной из одобрительно встреченных программистами инициатив, реализующихся в рамках акции Hack Week, стала публикация исходного кода приложения Zulip – веб-приложения для общения между собой разработчиков в сфере IT-технологий.

Объединение ОС Android и Chrome

17.11.2015
Слухи об объединении двух крупнейших ОС компании Google, Android и Chrome, гуляют по Интернету уже более 5 лет, но до сих пор этого не случилось, хотя очевидно, что с течением времени эти ОС становятся всё более похожими: так, в последнее время появилось немало Android-устройств, к которым прилагаются клавиатуры, а Chrome OS «научилась» работать с сенсорными экранами.

Конференция Linux Piter 2015

15.11.2015
Уже почти через неделю в Санкт-Петербурге впервые в истории пройдёт конференция, посвящённая проблемам свободного программного обеспечения – Linux Piter 2015.