Lokalna optimizacija

  • Lokalna optimizacija je pristop, ki ga običajno uporabimo pri reševanju "težkih" problemov, npr. problema potujočega trgovca.

  • Primer.

  • Za graf z vozlišči imamo dopustnih rešitev.
    5 24
    10 3.6 ∙ 105
    20 1.2 ∙ 1017
    50 6.1 ∙ 1062
    100 9.3 ∙ 10155

  • Ideja: iščemo "lokalne optimume" in upamo, da so tudi globalni optimumi.

Relacija sosednosti

  • Definicija. Naj bo množica. Relacija je relacija sosednosti, če je refleksivna () in simetrična ().
    • Za element je množica soseščina elementa .
    • Element je -lokalni minimum (-lokalni maksimum) funkcije , če velja ().
  • Definicija. Relacija je natančna za , če je -lokalni minimum tudi globalni minimum.

Metoda za iskanje globalnih minimumov

  • Izberemo naključen , in nastavimo .
  • Preverimo, če je -lokalni minimum - če je, postopek končamo
  • Sicer obstaja , da .
  • Postavimo in ponavljamo.
  • Če se postopek konča, smo našli -lokalni minimum.
  • Postopek večkrat ponovimo in izberemo najboljšega izmed dobljenih -lokalnih minimumov.

Primeri

  • 1. , izberemo . Naj bo .

    • Relacija ni natančna za splošne , je pa natančna za konveksne .

  • 2. Množica dopustnih rešitev linearnega programa je politop (angl. polytope).

    • Globalni minimum in maksimum sta dosežena na ekstremni točki, torej na oglišču.
    • Naj bo torej množica oglišč in definirajmo relacijo tako, da velja natanko tedaj, ko sta in na istem robu.
    • Prej opisana metoda za je ravno simpleksna metoda.
    • Relacija je natančna za ciljno funkcijo .

Primer: najcenejše vpeto drevo

3. povezan graf, uteži povezav.

  • Naj bo množica (množic povezav ) vpetih dreves v in funkcija cene vpetega drevesa.
  • To je problem najcenejšega vpetega drevesa - za reševanje lahko uporabimo Primov ali Kruskalov algoritem.
  • Definiramo relacijo , tako da velja .
  • Relacija je natančna za (brez dokaza).

Primer: problem potujočega trgovca

4. Problem potujočega trgovca: povezan graf, uteži povezav.

  • Naj bo množica Hamiltonovih ciklov v in funkcija cene Hamiltonovega cikla.

  • Relacijo definiramo tako, da sta dva Hamiltonova cikla sosedna, če lahko "prevežemo" dve povezavi na ciklu.

Nenatančnost relacije

  • Relacija ni natančna.

  • Naj bo , in Hamiltonov cikel z , ter

  • Potem velja:

  • je torej -lokalni minimum, ni pa tudi globalni minimum.

Protiprimer

  • Začetna rešitev:

    • Cena: 25

  • Prva vrsta soseda:

    • Cena: 35

Protiprimer (2)

  • Druga vrsta soseda:

    • Cena: 26

  • Optimalna rešitev:

    • Cena: 22