Табу-пошук

Табу-пошук (ТП) — метод локального пошуку для математичної оптимізації. Створений Фредом У. Гловером в 1986 році[1] і формалізований в 1989[2].

Визначення

Табу-пошук (ТП) є мета-евристичним алгоритмом, який веде локальний пошук, щоб запобігти його від попадання в пастку в передчасних локальних оптимумах, забороняючи ті переміщення, які змушують повертатися до попередніх рішень і циклічної роботи. ТП починається з вихідного рішення. На кожній ітерації генерується окіл рішень, і найкраще з цього околу вибирається як нове рішення. Певні атрибути попередніх рішень зберігаються в табу-списку, який оновлюється в кінці кожної ітерації. Вибір найкращого рішення в околі відбувається таким чином, що він не приймає жодного з заборонених атрибутів. Найкраще допустиме рішення в даний час, оновлюється, якщо нове поточне рішення краще і допустиме. Процедура триває, поки не виконається будь-який з двох критеріїв зупину, якими є максимальне число виконуваних ітерацій і максимальне число ітерацій, під час яких чинне рішення не поліпшується.

Фред У. Гловер запропонував наступну схему локального пошуку:

нехай для задачі дискретної оптимізації

    

вдалося знайти деяке допустиме рішення . Розглянемо окіл точки і знайдемо рішення задачі

    

Позначимо його через . Розглянемо тепер окіл , знайдемо точку і т. д. до тих пір, поки . Якщо , то точка є локальним оптимумом.

Ідея алгоритму «Пошуку з Заборонами» полягає в тому, щоб не зупинятися у локальному оптимумі, як це запропоновано в алгоритмах локального спуску, а продовжити пошук, керуючись тими ж правилами, забороняючи відвідування вже пройдених точок.

На -му кроці алгоритму точка знаходиться з рішення задачі

  

Множина виступає як список заборон, що і послужило приводом для назви алгоритму. Цей список поповнюється на кожному кроці новою точкою. Очевидно, що якщо стара інформація не буде видалятися зі списку, то працездатність алгоритму буде падати з ростом числа ітерацій. Тому довжина списку обмежується зверху деякою константою , і список заборон містить тільки останні точок. Перевірка і поповнення списку може виявитися досить трудомісткою операцією. Тому, іноді доцільно зберігати не самі рішення , , а або функції від них (наприклад, значення цільової функції), або номера змінюваних координат, атрибути переходу від до . Позначимо через частину околу , взяту випадковим чином. Тоді алгоритм пошуку із заборонами можна представити в наступному вигляді.

Алгоритм ТП

1. Обираємо початкове рішення , вважаємо . Формуємо порожній список заборон.
2. Знаходимо нове рішення таке, що

    а)  
    б) ;
    в) перехід   не є забороненим або  .

3. Переходимо в нову точку .
Змінюємо список заборон.

    Якщо  , то змінюємо рекорд  .

4. Якщо виконаний критерій зупинки, то STOP, інакше йти на п.2.

Як критерій зупинки використовується або зупинка по числу ітерацій, або необхідна точність по відношенню до заданої нижньої межі. Початкове рішення вибирається за допомогою якогось простого алгоритму. Змінюючи довжину списку заборон, можна керувати процесом пошуку. При зменшенні довжини, інтенсифікується пошук в поточній області, збільшення довжини сприяє переходу до іншої області. Як околиці можна розглядати безліч всіх рішень, які виходять з поточного рішення зміною однією з координат. У 1992 році Файгл і Керн[3] запропонували імовірнісну версію методу TS, який при кількості ітерацій прагнучих до нескінченності, сходиться до глобального оптимуму, що, втім, властива більшості імовірнісних алгоритмів. Так рандомізація околиці скорочує трудомісткість алгоритму на кроці 2 і вносить елемент випадковості при виборі напрямку спуску. Якщо рандомізована околиця становить від 1 до 10 відсотків від початкової, то алгоритм не зациклюється навіть без списку заборон. Алгоритм TS застосовувався до широкого кола завдань дискретної оптимізації[4], показав високу працездатність і на сьогодні є однією з найпопулярніших імовірнісних евристик. Одне з можливих застосувань методу «Пошук з заборонами» для вирішення задач нерегулярного розкрою — упаковки (Р-У) запропоновано в роботі[5] польськими авторами Блазевічем, Хаврулюком і Валковяком.

Псевдокод

Псевдокод алгоритму табу-пошуку для мінімізації функції витрат. Псевдокод показаує простий алгоритм табу-пошуку з використанням короткочасної пам'яті, без проміжних і довгострокових управлінь пам'яттю.

    Input:  
    Output:  
      ConstructInitialSolution()
    TabuList 
    While ( StopCondition())
        CandidateList 
        For (  )
            If ( ContainsAnyFeatures(, TabuList))
                CandidateList  
            End
        End
          LocateBestCandidate(CandidateList)
        If (Cost()  Cost())
            TabuList  FeatureDifferences(, )
            While (TabuList > )
                DeleteFeature(TabuList)
            End
        End
    End
    Return ()

Приклад

Задача комівояжера

Задача комівояжера часто використовується, щоб показати функціональність табу-пошуку.

Зада́ча комівояже́ра (комівояжер — бродячий торговець; англ. Travelling Salesman Problem, TSP; нім. Problem des Handlungsreisenden) полягає у знаходженні найвигіднішого маршруту, що проходить через вказані міста хоча б по одному разу. В умовах завдання вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості тощо. Зазвичай задано, що маршрут повинен проходити через кожне місто тільки один раз, в такому випадку розв'язок знаходиться серед гамільтонових циклів.

Наприклад, якщо місто A і місто B розташовані поруч одне з одним, в той час як місто C розташоване далі, загальна пройдена відстань, буде коротшою, якщо міста А і Б відвідали одне за одним перед приїздом до міста С. Оскільки знаходження оптимального рішення до задачі комівояжера є NP-повним завданням, евристичні наближені методи (наприклад, локальний пошук) корисні для розробки близьких до оптимальних рішень.

Табу-пошук може бути використаний для пошуку задовільного рішення для задачі комівояжера (тобто, рішення, яке задовольняє критерію адекватності, а не абсолютно оптимальне рішення). По-перше, пошук із заборонами починається з початкового рішення, яке може бути згенероване випадково, або за допомогою якогось алгоритму найближчого сусіда. Для створення нового рішення, два міста, які відвідують в потенційному рішення, змінюються місцями. Загальна відстань подорожі між усіма містами використовується для оцінки ідеального рішення, в порівнянні з іншим. Для запобігання циклів і, щоб не застрягти в локальних оптимумах, рішення буде додано до списку табу, якщо воно буде задовольняти рішення в околиці.

Нові рішення продовжують створюватися до появи деяких стоп-критеріїв, таких як довільне число ітерацій. Коли табу-пошук припиняється, повертається краще рішенням — рішення з найкоротшою відстанню, під час відвідування всіх міст.

Посилання

  1. F. Glover and C. McMillan (1986). «The general employee scheduling problem: an integration of MS and AI». Computers and Operations Research.
  2. Fred Glover (1989). «Tabu Search». ORSA Journal on Computing 1 (2).
  3. Faigle U., Kern W. Some convergence results for probabilistic tabu search. ORSA Journal on Computing 4(1), pp.32-37,1992.
  4. Glover F., Laguna M. Tabu search in modern heuristic techniques for combinatorial problems, Blackwell Publishing, 1992.
  5. Blazewicz J., Hawryluk P., Walkowiak R. Using a tabu search approach for solving the two-dimensional irregular cutting problem. — Annals of OR, 41(1-4), pp.313-325, 1993.

Джерела

Zeynep Özyurt, Deniz Aksen, Necati Aras. Открытая задача маршрутизации транспортного средства с временными сроками: методы решения и применения. (перевод Александрова О. А.)


Read other articles:

Artikel ini perlu diwikifikasi agar memenuhi standar kualitas Wikipedia. Anda dapat memberikan bantuan berupa penambahan pranala dalam, atau dengan merapikan tata letak dari artikel ini. Untuk keterangan lebih lanjut, klik [tampil] di bagian kanan. Mengganti markah HTML dengan markah wiki bila dimungkinkan. Tambahkan pranala wiki. Bila dirasa perlu, buatlah pautan ke artikel wiki lainnya dengan cara menambahkan [[ dan ]] pada kata yang bersangkutan (lihat WP:LINK untuk keterangan lebih lanjut...

 

 

Patung Daikokuten di kuil Kanda, Tokyo, Jepang. Daikokuten (大黒天code: ja is deprecated ) adalah dewa kekayaan dan kemakmuran, salah satu Tujuh Dewa Keberuntungan menurut kepercayaan tradisional Jepang. Daikokuten merupakan asimilasi dari Siwa, dewa dalam agama Hindu. Namanya merupakan padanan kata Mahakala (nama lain Siwa, bahasa Sanskerta) dalam bahasa Jepang. Nama Mahakala terdiri dari kata mahā (महत्; besar) dan kāla (काल; gelap), diartikan sebagai kegelapan raya, seda...

 

 

This article does not cite any sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Two Fathers TV series – news · newspapers · books · scholar · JSTOR (October 2015) (Learn how and when to remove this template message) Taiwanese TV series or program Two FathersPromotional posterAlso known as兩個爸爸GenreTaiwanese dramaWritten byShaohui TingShiheng Hua...

Elections in Louisiana Federal government Presidential elections 1812 1816 1820 1824 1828 1832 1836 1840 1844 1848 1852 1856 1860 1864 1868 1872 1876 1880 1884 1888 1892 1896 1900 1904 1908 1912 1916 1920 1924 1928 1932 1936 1940 1944 1948 1952 1956 1960 1964 1968 1972 1976 1980 1984 1988 1992 1996 2000 2004 2008 2012 2016 2020 2024 Presidential primaries Democratic 2000 2004 2008 2012 2016 2020 Republican 2004 2008 2012 2016 2020 U.S. Senate elections 1812 1813 1813 sp 1817 1818 1818 sp 181...

 

 

Cochliomyia merupakan hama pertama yang berhasil dihilangkan dari suatu daerah menggunakan teknik serangga steril Teknik Serangga Steril atau Teknik Serangga Mandul adalah suatu metode pengurangan jumlah populasi serangga tertentu dalam suatu ekosistem menggunakan serangga steril atau serangga mandul. Serangga mandul ini telah direkayasa dengan iradiasi sinar gambar.[1] Teknik ini telah digunakan secara internasional selama lebih dari 50 tahun.[2] Teknik ini telah diterapkan k...

 

 

Study of the relationship of microorganisms with their environment Environmental microbiology redirects here. For the journal, see Environmental Microbiology (journal). The great plate count anomaly. Counts of cells obtained via cultivation are orders of magnitude lower than those directly observed under the microscope. This is because microbiologists are able to cultivate only a minority of naturally occurring microbes using current laboratory techniques, depending on the environment.[1&...

Perang ChacoBagian dari periode antar perangBolivia dan Paraguay sebelum Perang tahun 1932Tanggal15 Juni 1932 – 10 Juni 1935LokasiGran Chaco, Amerika SelatanHasil Kemenangan ParaguayPerubahanwilayah Kebanyakan wilayah Gran Chaco diberikan kepada Paraguay. Bolivia menguasai zona strategis dan pelabuhan di sungai Paraguay.Pihak terlibat  Bolivia  ParaguayTokoh dan pemimpin Jendral Hans KundtJendral Enrique Peñaranda Castillo José Félix EstigarribiaKekuatan 250 000 150 000Korban ~...

 

 

American professional wrestler (born 1978) For the Australian soccer player, see Adam Pearce (soccer). Adam PearcePearce as NWA Worlds Heavyweight Champion in 2012Birth nameAdam John PearceBorn (1978-06-24) June 24, 1978 (age 45)Lake Forest, Illinois, U.S.Alma materUniversity of PhoenixSpouse(s) Sarah Muravez ​(m. 2002)​Children2Professional wrestling careerRing name(s)Adam O'BrienAdam PearceEl Hijo de Matt ClassicMasked Spymaster IIScrap Iron Adam PearceU.S....

 

 

2004 action-adventure video game 2004 video gameHarry Potter and the Prisoner of AzkabanPC cover artDeveloper(s) KnowWonder (Microsoft Windows) Griptonite Games (Game Boy Advance) EA UK (PlayStation 2, Xbox, GameCube) Publisher(s)Electronic ArtsDirector(s)Phillip Trumbo (PC, GBA)Producer(s)Michael Waite, Steve Reddoch (PC)Designer(s)Christopher Vucetich, Chris Brockett, Ed Byrne, Del Chafe III (PC)Tony Sharma, Tom Snider, Brian C. McAuliffe, Dream Smith (GBA)Programmer(s)Michael Dorgan (GBA)A...

Хип-хоп Направление популярная музыка Истоки фанкдискоэлектронная музыкадабритм-энд-блюзреггидэнсхоллджаз[1]чтение нараспев[англ.]исполнение поэзииустная поэзияозначиваниедюжины[англ.]гриотыскэтразговорный блюз Время и место возникновения Начало 1970-х, Бронкс, Н...

 

 

2023 single by Ava MaxGhostMerk & Kremont remix coverSingle by Ava Maxfrom the album Diamonds & Dancefloors ReleasedMarch 16, 2023 (2023-03-16)Genre Synth-pop house Length3:01LabelAtlanticSongwriter(s) Amanda Ava Koci Henry Walter Uzoechi Emenike Producer(s)CirkutAva Max singles chronology One Of Us (2023) Ghost (2023) Car Keys (Ayla) (2023) VisualizerGhost on YouTube Ghost is a song by American singer Ava Max from her second studio album, Diamonds & Dancefloors. Th...

 

 

Selection of different dog breeds This list of dog breeds includes both extant and extinct dog breeds, varieties and types. A research article on dog genomics published in Science/AAAS defines modern dog breeds as a recent invention defined by conformation to a physical ideal and purity of lineage.[1] According to BigThink, over 40% of the world’s dog breeds come from the United Kingdom, France and Germany. It states: Great Britain and France are the ground zero of dog fancying, wi...

Questa voce o sezione sull'argomento software non cita le fonti necessarie o quelle presenti sono insufficienti. Commento: nessuna fonte Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento. Background Intelligent Transfer ServicesoftwareGeneresoftware che opera in background (non in lista) SviluppatoreMicrosoft Data prima versioneOttobre 2001 Ultima&#...

 

 

В Википедии есть статьи о других людях с именем Михаил. Архиепископ Михаил Архиепископ Вологодский и Великоустюжский 27 декабря 1979 — 23 февраля 1993 Церковь Русская православная церковь Предшественник Феодосий (Дикун) Преемник Максимилиан (Лазаренко) Архиепископ Аст�...

 

 

У этого термина существуют и другие значения, см. Литовский полк. 51-й пехотный Литовский Его Императорского Высочества Наследника Цесаревича полк Годы существования 22 октября 1809 — 1918 Страна  Российская империя Входит в 13-я пех. див-я, 7 АК, ОдВО Тип пехота Дислокация Сим...

Not to be confused with Kanaya Station or Kamaya Station (Aichi). Railway station in Kikonai, Hokkaido, Japan Kamaya Station釜谷駅Kamaya Station, September 2022General informationLocationKikonai, Kamiiso District, HokkaidoJapanOperated bySouth Hokkaido Railway CompanyLine(s)South Hokkaido Railway LineHistoryOpened1930LocationKamaya StationLocation within HokkaidoShow map of HokkaidoKamaya StationKamaya Station (Japan)Show map of Japan Kamaya Station (釜谷駅, Kamaya-eki) is a railway sta...

 

 

Kurdish people in Denmark Ethnic group Kurds in DenmarkTotal population25,000 (2016 Kurdish Institute of Paris estimate[1]) - 30,000[2]LanguagesDanish, KurdishReligionIslamRelated ethnic groupsKurds in Finland, Kurds in Norway Kurds in Sweden   Part of a series on: Kurdish history and Kurdish culture People List of Kurds Population Homeland Kurdistan Turkey (Northern Kurdistan) Iran (Eastern Kurdistan) Iraq (Southern Kurdistan) Syria (Western Kurdistan) Diaspora Armenia A...

 

 

هذه المقالة بحاجة لصندوق معلومات. فضلًا ساعد في تحسين هذه المقالة بإضافة صندوق معلومات مخصص إليها. قدمت النيجر فيلمًا لجائزة الأوسكار لأفضل فيلم بلغة أجنبية لأول مرة في عام 2018.[1][2] يتم تسليم الجائزة سنويًا من قبل أكاديمية فنون وعلوم الصور المتحركة إلى الأفلام السي�...

For other places with the same name, see Plumstead (disambiguation). Human settlement in EnglandPlumsteadPlumstead Common Road in 2015PlumsteadShow map of Royal Borough of GreenwichPlumsteadLocation within Greater LondonShow map of Greater LondonPopulation16,736 (2011 Census Ward)[1]OS grid referenceTQ445785London boroughGreenwichCeremonial countyGreater LondonRegionLondonCountryEnglandSovereign stateUnited KingdomPost townLONDONPostcode districtSE1...

 

 

U.S. National Championships 1907Sport Tennis Data20 agosto - 28 agosto (uomini)25 giugno - 2 luglio (donne) Edizione27ª CategoriaGrande Slam (ITF) LocalitàNewport e Filadelfia, USA CampioniSingolare maschile William Larned Singolare femminile Evelyn Sears Doppio maschile Fred Alexander / Harold Hackett Doppio femminile Marie Wimer / Carrie Neely Doppio misto May Sayres / Wallace Johnson 1906 1908 Gli U.S. National Championships 1907 (conosciuti oggi come US Open) sono stati la 27ª edizione...