Резюме

В тази статия представяме вариация на параметъра на алгоритъма за извадка на фиктивно възпроизвеждане без параметри, която улеснява бързото решаване на детерминирани задачи за динамично програмиране. Неговата процедура за случайно прекъсване на връзките придава естествена произволност на алгоритъма, която му пречи да „заседне“ при локално оптимално решение и позволява откриването на оптимален път в краен брой итерации. Освен това илюстрираме чрез приложение за морска навигация, че на практика алгоритъмът за извадка на фиктивна игра без параметри намира висококачествено решение само след няколко повторения, за разлика от традиционните методи.

Това е визуализация на абонаментното съдържание, влезте, за да проверите достъпа.

Опции за достъп

Купете единична статия

Незабавен достъп до пълната статия PDF.

Изчисляването на данъка ще бъде финализирано по време на плащане.

Абонирайте се за списание

Незабавен онлайн достъп до всички издания от 2019 г. Абонаментът ще се подновява автоматично ежегодно.

Изчисляването на данъка ще бъде финализирано по време на плащане.

игра

Препратки

Denardo, E.V .: Динамично програмиране. Dover Publications Inc, Минеола, Ню Йорк (2003)

Bertsekas, D.P .: Динамично програмиране и оптимален контрол, 3-то изд. Атина Научен, Белмонт (2007)

Androulakis, I.P .: Динамично програмиране: контрол на запасите динамично програмиране: Управление на запасите. В: Floudas, C.A., Pardalos, P.M. (ред.) Енциклопедия за оптимизация, стр. 853–856. Спрингър, САЩ (2009). doi: 10.1007/978-0-387-74759-0_149

Khaledi, H., Reisi-Nafchi, M .: Модел за динамично планиране на производството: подход за динамично програмиране. Int J Adv Manuf Technol 67(5–8), 1675–1681 (2013). doi: 10.1007/s00170-012-4600-7

Санчо, Н .: Динамично програмно решение на проблем с най-кратък път с ограничения във времето за движение и паркиране. J. Math. Анален. Приложение. 166(1), 192–198 (1992). doi: 10.1016/0022-247X (92) 90335-B. http://www.sciencedirect.com/science/article/pii/0022247X9290335B

Righini, G., Salani, M .: Нови алгоритми за динамично програмиране за елементарния проблем с най-кратък път, ограничен. Мрежи 51(3), 155–170 (2008). doi: 10.1002/net.v51: 3

Plant, W.J., Keller, W.C., Hayes, K .: Едновременно измерване на океанските ветрове и вълни с въздушен кохерентен радар с реална апертура. J. Atmos. Oceanic Technol. 22., 832–846 (2005)

Johnson, J.T., Burkholder, R.J., Toporkov, J.V., Lyzenga, D.R., Plant, W.J .: Числено изследване на извличането на профили на височината на морската повърхност от радарни данни с нисък пасищен ъгъл. IEEE Trans. Геоски. Дистанционно Sens. 47(6), 1641–1650 (2009)

Alford, L. K., Beck, R. F., Johnson, J. T., Lyzenga, D., Nwogu, O., Zundel, A .: Проектиране, внедряване и оценка на система за прогнозиране на околната среда и движението на кораба. В: 30-ти симпозиум по морска хидродинамика. Хобарт, Тасмания, Австралия (2014)

Nwogu, O.G .: Взаимодействие на вълни с крайна амплитуда с вертикално срязани токови полета. J. Fluid Mech. 627, 179–213 (2009)

Nwogu, O.G., Lyzenga, D.R .: Оценка на повърхностното вълново поле от кохерентни морски радари. IEEE Geosci. Дистанционно Sens. Lett. 7(4), 631–635 (2010)

Zhang, X., Bandyk, P., Beck, R.F .: Морски изчисления, използващи потоци от двойно тяло. Приложение Ocean Res. 32(4), 471–482 (2010)

Dreyfus, S.E .: Оценка на някои алгоритми с най-кратък път. Опер. Рез. 17(3), 395–412 (1969)

Ahuja, R. K., Mehlhorn, K., Orlin, J., Tarjan, R.E .: По-бързи алгоритми за проблема с най-краткия път. JACM 37(2), 213–223 (1990). doi: 10.1145/77600.77615

Ahuja, R. K., Magnanti, T. L., Orlin, J. B.: Мрежови потоци. Prentice Hall, Englewood Cliffs (1993)

Schrijver, A .: Комбинаторна оптимизация: многогранници и ефективност, кн. 24. Springer Science & Business Media, Берлин (2003)

Пърл, Дж .: Евристика: Интелигентни стратегии за търсене за решаване на компютърни проблеми. Адисън-Уесли, Рединг (1984)

Губичев, А., Бедатур, С., Зауферт, С., Вайкум, Г.: Бърза и точна оценка на най-кратките пътеки в големи графики. В: Сборник от 19-та международна конференция на ACM за управление на информация и знания, CIKM ’10, стр. 499–508. ACM, Ню Йорк, Ню Йорк (2010). doi: 10.1145/1871437.1871503

Brown, G.W .: Итеративно решение на игри чрез фиктивна игра. В: Koopmans, T.C. (съст.) Анализ на дейността на производството и разпределението, гл. XXIV, стр. 374–376. Уайли, Ню Йорк (1951)

Робинсън, Дж .: Итеративен метод за решаване на игра. Ан. Математика. 54(2), 296–301 (1951)

Monderer, D., Shapley, L.S .: Фиктивно свойство на игра за игри с идентични интереси. J. Econ. Теория 68(14), 258–265 (1996)

Lambert, T.J.I., Epelman, M.A., Smith, R.L .: Фиктивен игрови подход към мащабната оптимизация. Опер. Рез. 53(3), 477–489 (2005)

Cheng, S.F., Epelman, M.A., Smith, R.L .: CoSIGN: паралелен алгоритъм за координирано управление на сигнала за движение. IEEE Trans. Intell. Транс. Сист. 7(4), 551–564 (2006)

Garcia, A., Reaume, D., Smith, R.L .: Фиктивна игра за намиране на оптимално маршрутизиране на системата в динамични мрежи за трафик. Транс. Рез. Б. 34(2), 147–156 (2000)

Garcia, A., Patek, S.D., Sinha, K .: Децентрализиран подход за дискретна оптимизация чрез симулация: приложение към мрежовия поток. Опер. Рез. 55(4), 717–732 (2007)

Ghate, A., Cheng, S.F., Baumert, S., Reaume, D., Sharma, D., Smith, R.L .: Примерна фиктивна игра за стохастични динамични програми с много действия. IIE Trans. 46(7), 742–756 (2014)

Сисикоглу, Е .: Разпределени алгоритми, базирани на фиктивна игра за почти оптимално последователно вземане на решения. Доцент доктор. дисертация, Университетът в Мичиган, Ан Арбър, Мичиган (2009)

Epelman, M.A., Ghate, A., Smith, R.L .: Пробна фиктивна игра за приблизително динамично програмиране. Изчисляване. Опер. Рез. 36(12), 1705–1718 (2011)

Сисикоглу, Е., Епелман, М. А., Смит, Р. Л.: Изваден фиктивен алгоритъм за обучение, базиран на игра за безкрайни процеси на вземане на решения от марковски хоризонт. В: S. Jain, R.R. Creasey, J. Himmelspach, K.P. Уайт, М. Фу (ред.) Сборник от зимната симулационна конференция през 2011 г., стр. 4086–4097 (2011)

Пауъл, У.Б .: Приблизително динамично програмиране: Решаване на проклятията на измереността, кн. 703. Уайли, Хобокен (2007)

Si, J., Barto, A.G., Powell, W.B., Wunsch, D .: Наръчник за обучение и приблизително динамично програмиране (IEEE Press Series on Computational Intelligence). Wiley-IEEE Press, Ню Йорк (2004)

Marden, J.R., Young, H.P., Arslan, G., Shamma, J.S .: Динамика, базирана на изплащане за мултиплейър слабо ациклични игри. SIAM J. Control Optim. 48(1), 373–396 (2009). doi: 10.1137/070680199

Buşoniu, L., Babuška, R., De Schutter, B., Ernst, D .: Укрепващо обучение и динамично програмиране с помощта на функционални апроксиматори. CRC Press, Boca Raton (2010) doi: 10.1201/9781439821091

Врабие, Д., Вамвудакис, К. Г., Луис, Ф. Л.: Оптимален адаптивен контрол и диференциални игри чрез подсилващи учебни принципи. Институтът по инженерство и технологии, Лондон (2012)

Zermelo, E .: Über das navigationproblem bei ruhender oder veränderlicher windverteilung. З. Андрю. Математика. Мех. 11.(2), 114–124 (1931)

Фолкнер, Ф. Д.: Общ числен метод за определяне на оптимални маршрути на кораба. Навигация 10(2), 143–148 (1963)

Faulkner, F.D .: Числени методи за определяне на оптимални маршрути на кораба. Навигация 10(4), 351–367 (1963)

Papadakis, N.A., Perakis, A.N .: Детерминирано маршрутизиране на кораби с минимално време. Опер. Рез. 38(3), 426–438 (1990)

Perakis, A.N., Papadakis, N.A .: Нови модели за минимално време на маршрута на времето на кораба. Soc. Военноморска арка. Морски инж. Транс. 96, 247–269 (1988)

Perakis, A.N., Papadakis, N.A .: Минимално време за плаване на плавателни съдове в среда, зависима от времето. Транс. Sci. 23.(4), 266–276 (1989)

Kimball, J.C., Story, H .: Принцип на Ферма, принцип на Хюйгенс, оптика и стратегия на ветроходството на Хамилтън. Евро. J. Phys. 19., 15–24 (1998)

Philpott, A.B., Sullivan, R.M., Jackson, P.S .: Прогнозиране на скоростта на яхта с помощта на математическо програмиране. Евро. J. Oper. Рез. 67(1), 13–24 (1993)

Allsopp, T., Mason, A., Philpott, A.B .: Оптимални ветроходни маршрути с несигурно време. В: Сборник от 35-та годишна конференция на оперативното изследователско общество на Нова Зеландия, стр. 65–74 (2000)

Philpott, A.B .: Стохастична оптимизация и състезания с яхти. В: Приложения на стохастично програмиране, MPS/SIAM Ser. Оптим., об. 5, стр. 315–336. SIAM, Филаделфия, Пенсилвания (2005)

Philpott, A.B., Mason, A .: Оптимизиране на маршрутите на яхтите при несигурност. В: 15-ият симпозиум за ветроходни яхти Cheasapeake (2001)

Mitchell, J.S.B .: Геометрични най-кратки пътища и оптимизация на мрежата. В: Наръчник по изчислителна геометрия, стр. 633–701. Северна Холандия, Амстердам (2000)

Lanthier, M., Maheshwari, A., Sack, J.R .: Най-къси анизотропни пътеки по терени. В: Автомати, езици и програмиране (Прага, 1999), Бележки по лекции в Comput. Sci., об. 1644, с. 524–533. Спрингър, Берлин (1999)

Роу, Северна Каролина: Получаване на оптимални пътеки за мобилни роботи с негладки анизотропни функции на разходите, като се използват разсъждения за качествено състояние. Международна Дж. Роб. Рез. 16.(3), 375–399 (1997)

Rowe, N.C., Ross, R. S.: Оптимално планиране на пътя без решетка през произволно очертан терен с анизотропни ефекти на триене и гравитация. IEEE Trans. Грабя. Автомат. 6(5), 540–553 (1990)

Sun, Z., Rief, J.H .: За намиране на минимизиращи пътеки по терени. IEEE Trans. грабя. 21.(1), 102–114 (2005)

Nilim, A., El Ghaoui, L., Hansen, M., Duong, V .: Управление на въздушното движение въз основа на траектория (TB-ATM) при метеорологична несигурност. В: Сборник от четвъртия международен семинар за научноизследователска и развойна дейност по управление на въздушното движение ATM. Санта Фе, Ню Мексико (2001)

Nilim, A., El Ghaoui, L .: Алгоритми за управление на въздушния трафик в стохастична среда. Известия от американската контролна конференция 4, 3429–3434 (2004)

Fang, M.C., Luo, J.H .: За поддържане на следите и намаляване на търкалянето на кораба в произволни вълни, използвайки различни контролери за плъзгащ режим. Ocean Eng. 34, 479–488 (2007)

Treakle, T.W.I., Mook, D.T., Liapis, S.I., Nayfeh, A.H .: Метод във времева област за оценка на използването на движещи се тежести за намаляване на движението на търкалянето на кораба. Ocean Eng. 27(12), 1321–1343 (2000)

Smith, T.C., Thomas III, W.L .: Проучване на устройства за намаляване на движението на кораба. Департаментен доклад SHD-1338-01, Изследователски център на Дейвид Тейлър, Бетесда, Мериленд 20084-5000 (1990)

Долинская, И.С .: Оптимално намиране на път в среда, зависима от посока, местоположение и време. Нав. Рез. Логист. Кварта. 59(5), 325–339 (2012)

Dijkstra, E.W .: Бележка за два проблема във връзка с графики. Число. Математика. 1(1), 269–271 (1959)

Рос, С. М.: Стохастични процеси, 2-ро изд. Уайли, Ню Йорк (1995)

Zwillinger, D., Kokoska, S .: Таблици и формули за стандартни вероятности и статистика на CRC. CRC Press, Boca Raton (1999)

Фосен, Т. И .: Насоки и контрол на океанските превозни средства. Уайли, Ню Йорк (1994)

Dubins, L.E .: На криви с минимална дължина с ограничение на средната кривина и с предписани начални и крайни позиции и допирателни. Амери. J. Math. 79, 497–516 (1957)

Sussmann, H.J., Tang, G .: Най-кратък път за автомобила Reeds-Shepp: разработен пример за използване на геометрични техники в нелинейно оптимално управление. Техн. Представител SYCON-91-10, Rutgers Center for Systems and Control (1991)

Boissonnat, J.D., Cérézo, A., Leblond, J .: Най-къси пътеки с ограничена кривина в равнината. J. Intell. Грабя. Сист. 11.(1–2), 5–20 (1994)

Alden, J.M., Smith, R.L .: Процедури на подвижен хоризонт в нехомогенни процеси на вземане на решения по Марков. Опер. Рез. 40(доп. 2), S183 – S194 (1992)

Lee, C.Y., Denardo, E.V .: Хоризонти на планиране на търкаляне: граници на грешки за динамичния модел на размера на партидата. Математика. Опер. Рез. 11.(3), 423–432 (1986)

Ovacikt, I.M., Uzsoy, R .: Алгоритми на подвижния хоризонт за проблем с динамично планиране на една машина с зависими от последователността времена за настройка. Международна J. Prod. Рез. 32(6), 1243–1263 (1994)

Служба за военноморски изследвания: MURI-оптимално маневриране на кораб в еволюиращи нелинейни вълнови полета: Финална среща. Арлингтън, Вирджиния (2011)

Благодарности

Авторите биха искали да благодарят на Okey Nwogu и Fernando Tavares за тяхното съдействие при изпълнението и числените резултати. Тази работа беше подпомогната отчасти от Службата за военноморски изследвания чрез Мултидисциплинарната университетска изследователска инициатива (MURI) Оптимална производителност на плавателните съдове в еволюиращ грант за нелинейни вълнови полета (N00014-05-1-0537).

Информация за автора

Принадлежности

Катедра по индустриално инженерство и науки за управление, Северозападен университет, Еванстън, Илинойс, 60208, САЩ

Ирина С. Долинская

Катедра по индустриално и оперативно инженерство, Университет на Мичиган, Ан Арбър, Мичиган, 48109, САЩ

Марина А. Епелман и Робърт Л. Смит

Служба за управление на достъпа, клиника Майо, Рочестър, MN, 55905, САЩ

Есра Шишикоглу сър

Можете също да търсите този автор в PubMed Google Scholar

Можете също да търсите този автор в PubMed Google Scholar

Можете също да търсите този автор в PubMed Google Scholar

Можете също да търсите този автор в PubMed Google Scholar