...
  •  

    pokaż komentarz

    3 lata studiów logistycznych, a tu taka ciekawostka...

  •  

    pokaż komentarz

    Podoba mi się dynamika tej prezentacji.

  •  

    pokaż komentarz

    Ciekawy jest algorytm mrówkowy stworzony na podstawie obserwacji zachowań tych zwierząt:

    W najprostszej wersji schemat algorytmu mrówkowego wygląda następująco:
    Połączenia między miastami inicjowane są z pewną (niewielką) ilością feromonu. Pewna liczba mrówek umieszczona jest na losowo wybranych miastach.
    Mrówki poruszają się z miasta do miasta. Nie mogą wracać do miasta, w którym już były. Miasto do którego przemieści się mrówka wybierane jest losowo jednakże preferowane są miasta bliżej położone i te z większą ilością feromonu.
    Gdy wszystkie mrówki zakończą obchód wszystkich miast to feromon na wszystkich ścieżkach zmniejsza się o pewną wartość (parowanie). Ponadto feromon na ścieżkach, którymi przeszły mrówki zwiększa się o ilość odwrotnie proporcjonalną do całkowitej długości trasy danej mrówki (im krótsza trasa tym większy przyrost).

  •  

    pokaż komentarz

    Ciekawe, jak poradziłby sobie tabu search?

    •  

      pokaż komentarz

      @minuano68: UPS dla przykładu używa programu ORION. Tutaj można więcej o nim przeczytać http://www.forbes.com/sites/alexkonrad/2013/11/01/meet-orion-software-that-will-save-ups-millions-by-improving-drivers-routes/. Można też łatwo zauważyć korzyści wynikające ze stosowania takich algorytmów. Załóżmy, że optymalizacja jest w stanie zaoszczędzić kierowcy 30 minut mnożąc to przez liczbę kierowców i liczbę dni w roku przynosi to ogromną oszczędność czasu, a co za tym idzie, pieniędzy.

    •  

      pokaż komentarz

      @Pismak: Ciekawe, ile płacą za ten soft, skoro mogą aż tyle zaoszczędzić?

    •  

      pokaż komentarz

      @minuano68: dawno temu na studiach to badałem i tabu search radził sobie gorzej niż symulowane wyżarzanie. Za tym drugim przemawia też prostota implementacji. Testowałem jeszcze algorytm ewolucyjny i on też wypadł lepiej niż tabu search. Od razu zaznaczam, że to nie były poważne badania, więc nie należy tego co tutaj wypisuję brać za pewnik ;).

    •  

      pokaż komentarz

      @ghostface: Pewnie zależy od problemu. Tabu search był niezły w szeregowaniu zadań na procesorach. Tabu search moim zdaniem jest prosty. Szukasz lokalnie najlepszego rozwiązania, po czym dodajesz je na listę tabu, żeby móc przejść do zupełnie innych rozwiązań. I sprawdzasz, jak to działa dla różnej długości list tabu. Z głowy bym nie powiedział, jak działa symulowane wyżarzanie. Ten algorytm wydawał mi się trudniejszy.

    •  

      pokaż komentarz

      @ghostface:
      @minuano68: To chyba studiuję to samo, bo robię ten sam projekt. Porównanie czasu algorytmów tabu search, symulowanego wyżarzania i algorytmu genetycznego. Radzą sobie różnie, w zależności od wielkości instancji i dobranych parametrów/założeń przy implementacji każdego z nich. Symulowane wyżarzanie jest proste w implementacji i ma najlepsze wyniki dla małych instancji problemu (kilkadziesiąt wierzchołków), tabu search radzi sobie czasem lepiej, czasem gorzej, najlepiej w średnich instancjach, natomiast algorytm genetyczny radzi sobie najlepiej (zwłaszcza dla dużych instancji (kilkaset wierzchołków)), ale dla mniejszych wykonuje się zdecydowanie dłużej. Także jeśli iść na kompromis pomiędzy jakością i czasem wykonania, to wygra chyba tabu search na równi z symulowanym wyżarzaniem, ale plusem tego drugiego jest prostota wdrożenia i obsługi.

    •  

      pokaż komentarz

      @Mave: W-4 PWr, tak? Kto teraz to prowadzi, skoro zamknęli cały zakład?

    •  

      pokaż komentarz

      @ghostface: dawniej był to dla nas ZSZ - Zakład Szeregowania Zadań :-P

    •  

      pokaż komentarz

      @minuano68: Nie tak dawno na studiach jako część pracy licencjackiej bawiliśmy się między innymi metrycznym TSP. Tabu searcha nie sprawdzaliśmy. Dla małych instancji najlepiej wypadał Christofides wspierany Blossomem V. Wyżarzanie wypadało de facto gorzej niż zwykły hill climb. Monte Carlo Tree Search wypadał bardzo słabo. W obecnej chwili najlepszy algorytm to LKH to jest k-opt który się adaptuje do sytuacji.. magic.

    •  

      pokaż komentarz

      @ghostface: Tak ;) Wykład prowadzi dr Makuchowski i to nawet w ciekawy sposób, wydaje się być bardzo w porządku, zobaczymy jak z zaliczeniem. Projekt przejęła doktorantka, laboratorium ona + ktoś tam jeszcze, generalnie przedmiotem zajmują się teraz niezbyt znani ludzie co mnie cieszy, bo zaraz po wyjściu afery na światło dzienne krążyły plotki, że przedmiot przejmuje profesor "Ostateczny sumator" B.

    •  

      pokaż komentarz

      @WhosYourDaddy: Widzę, że mam pewne zaległości. Po studiach chyba nie tak łatwo znaleźć robotę, w której można by rozwiązywać takie problemy. Komuś się poszczęściło?

    •  

      pokaż komentarz

      minuano68
      @minuano68:
      @ghostface:
      @Mave:
      Takie pytanie panowie, a czy w takich problemach mają szanse implementacji algorytmy gradientowe? W obszarze w którym prowadzę badania: optymalizacji dowolnych funkcji bardzo wydajny jest algorytm Levenberga-Marquardta, spotkaliście się może z nim na waszych studiach?

    •  

      pokaż komentarz

      @staszko90: nie spotkałem się z tym algorytmem w kontekście tego problemu.

    •  

      pokaż komentarz

      @ghostface: Tak tylko z ciekawości pytam, bo w przypadku optymalizacji funkcji, algorytmy gradientowe są w większości przypadków o wiele, wiele szybsze i bardziej zbieżne niż algorytmy symulowanego wyżarzania i genetyczne. Ale warto wiedzieć gdzie można je zastosować. Dzięki wielki!

    •  

      pokaż komentarz

      @staszko90: Jak zadasz różniczkowalną funkcję ciągłą na przestrzeni problemu to masz szansę. Ja tutaj takiej funkcji nie widzę chyba, że powiemy że każdy wierzchołek ma mieć w sumie stopień wejścia 1 i wyjścia też 1 i dopuścimy krawędzie z wagą [0,1], no ale potem jakoś trzeba będzie zdyskretyzować (pewnie takie slowo nie istnieje, czyli przejsc do dziedziny liczb calkowitych) co nie wydaje sie oczywiste.

      @minuano68: Niet, co prawda jeden pisze teraz magisterke z jakiegos uogolnionego problemu plecakowego i po studiach jest szansa ze zostanie na uczelni, a reszta z nas jakies bardziej praktyczne rzeczy na magisterke robi, a potem do USA po $ :)

    •  

      pokaż komentarz

      @WhosYourDaddy: Dzięki, btw słowo którego szukałeś to skwantować:) (czyli zdyskretyzować w przestrzeni wartości funkcji)

  •  

    pokaż komentarz

    A prędkość na drogach też tu jest brana pod uwagę? Bo jak nie to jest to trasa najkrótsza, a nie najszybsza, a więc... czy to takie świetne rozwiązanie?

    •  

      pokaż komentarz

      @WesolyMorswin: Droga może być rozumiana również jako czas przejazdu. Można powiedzieć że dokonujesz transformacji z dziedziny odległości na dziedzinę czasu przejazdu. Wbrew pozorom to wcale nie jest takie trudne. Co więcej, idąc krok dalej można zrobić funkcję kosztów uwzględniają czas jazdy (koszty pracownika) i zużyte w tym czasie paliwo. Jak może zauważysz, sprowadza się to do tego samego co poprzednio, czyli wyznaczenia takich takich funkcji kosztów dla każdego połączenia i wykonania algorytmu optymalizującego.

    •  

      pokaż komentarz

      @WesolyMorswin: Koszt połączenia między wierzchołkami możesz kształtować dowolnie. To może być koszt przejazdu, odległość między miastami, zużycie paliwa, przepustowość dróg, ogólnie cokolwiek (możesz nawet uwzględnić kilka parametrów dla jednego połączenia, nadać im wagi i wyliczyć średnią kosztów). Aby było ciekawiej i trudniej, możesz także zabronić poruszania się niektórymi trasami albo zaznaczyć, ze daną trasą można poruszać się tylko w jednym kierunku.

    •  

      pokaż komentarz

      @WesolyMorswin: w praktyce jest też branych wiele innych rzeczy pod uwagę jak np. to do której pracuje dana firma gdzie ma dojść przesyłka albo jakiś okreslony czas dostarczenia. Kwestia co bierzesz pod uwagę

Dodany przez:

avatar P....k dołączył
1240 wykopali 1 zakopali 37.3 tys. wyświetleń