Distribueret begrænsning optimering

Distribueret begrænsning optimering er fordelt analog til begrænsning optimering. En DCOP er et problem, hvor en gruppe af agenter skal distributedly vælge værdier for en række variabler, således at prisen på et sæt af begrænsninger over variabler enten minimeres eller maksimeret.

Distribueret Constraint Tilfredshed er en ramme for at beskrive et problem i form af begrænsninger, der er kendt og håndhæves af forskellige deltagere. De begrænsninger er beskrevet på nogle variable med foruddefinerede domæner, og skal tildeles de samme værdier som de forskellige midler.

Problemer, der er defineret med denne ramme kan løses ved nogen af ​​de algoritmer, der foreslås for det.

Rammerne blev brugt under forskellige navne i 1980'erne. Den første kendte brug med det nuværende navn i 1990.

Definitioner

DCOP

En DCOP kan defineres som en tupel, hvor:

  •  er et sæt af agenter;
  •  er et sæt af variabler,;
  •  er et sæt af domæner ,, hvor hver er et endeligt sæt indeholder de værdier, som dens tilhørende variabel kan tildeles;
  •  er en funktion der kortlægger alle mulige variable opgave til en omkostning. Denne funktion kan også opfattes som definerende begrænsninger mellem variabler dog variablerne må ikke Hermitisk;
  •  er en funktion kortlægning variabler til deres tilknyttede agent. indebærer, at det er agent ansvar at tildele værdien af ​​variabel. Bemærk, at det ikke nødvendigvis er sandt, at der enten er en injektion eller surjection; og
  •  er en operatør, der samler alle de individuelle omkostninger for alle mulige variable opgaver. Dette er normalt opnås gennem opsummering: .

Formålet med et DCOP er at have hver agent tildele værdier til de tilknyttede variabler for at enten minimere eller maksimere for en given opgave af variablerne.

Kontekst

En Kontekst er en variabel opgave for et DCOP. Dette kan opfattes som en funktion kortlægning variabler i DCOP til deres aktuelle værdier:

Bemærk, at en sammenhæng er hovedsagelig en delvis løsning, og behøver ikke indeholde værdier for hver variabel i problemet; Derfor indebærer, at midlet ikke er tildelt en værdi til variablen. I betragtning af denne repræsentation, kan de "domæne" af funktionen opfattes som det sæt af alle mulige sammenhænge til DCOP. Derfor, i resten af ​​denne artikel vil vi må bruge begrebet sammenhæng som et input til funktionen.

Eksempel problemer

Distribueret graf farvelægning

Grafen farvestoffer problem er som følger: givet en graf og et sæt farver, tildele hvert hjørne ,, en farve ,, således at antallet af tilstødende knudepunkter med samme farve minimeres.

Som DCOP, er der et middel pr toppunkt, der er tildelt til at afgøre den tilhørende farve. Hver agent har en enkelt variabel, hvis tilknyttet domæne er af kardinalitet. For hver knude, skal du oprette en variabel i DCOP med domænet. For hvert par af tilstødende knuder, skaber en begrænsning af omkostningerne 1, hvis begge relaterede variabler tildeles den samme farve:

Målet er altså at minimere.

Distribueret multipel tornyster problem

Den distribuerede multiple variant af tornyster problemet er som følger: givet et sæt af genstande af varierende volumen og et sæt af rygsække af varierende kapacitet, tildele hvert element til et tornyster sådan, at mængden af ​​overløb minimeres. Lade være det sæt af elementer, være det sæt af rygsække, være en funktion kortlægning elementer til deres volumen, og være en funktion kortlægning rygsække til deres kapacitet.

At kode dette problem som et DCOP for hver oprette en variabel med tilhørende domæne. Så for alle mulige sammenhæng:

hvor er en funktion, således at

Algoritmer

DCOP algoritmer kan klassificeres i henhold til den søgestrategi, synkroniseringen mellem agenter, kommunikationen mellem agenter og den vigtigste kommunikation topologi. Vedtage, for eksempel, bruger bedst første søgning, asynkron synkronisering, punkt-til-punkt kommunikation mellem nabolande agenter i den begrænsning graf og en begrænsning træ som vigtigste kommunikation topologi.

Hybrider af disse DCOP algoritmer findes også. BnB-Vedtage for eksempel ændrer søgning strategi Vedtage fra bedst første søgning til dybde-først gren-og-bundne søgning.

  0   0
Forrige artikel Banksia solandri

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha