Кіріспе
Таратылған шектеулерді оңтайландыру (DCOP немесе DisCOP) – шектеулерді оңтайландырудың таратылған нұсқасы. DCOP – агенттер тобының айнымалылар жиыны үшін мәндерді таратылған түрде таңдауын қажет ететін мәселе, мұнда айнымалылар бойынша шектеулер жиынтығының құны ең төменге дейін азайттырылады. Таратылған шектеуді қанағаттандыру – нақты қатысушыларға (агенттерге) белгілі және орындалатын шектеулер арқылы мәселені сипаттаудың құрылымы. Шектеулер алдын ала анықталған салалары бар кейбір айнымалыларда сипатталады және әртүрлі агенттерге бірдей мәндермен сәйкес келуі керек. Осы құрылыммен шешілетін мәселелерді осы мақсатта жасалған кез келген алгоритммен шешуге болады. Бұл құрылым 1980 жылдары әртүрлі атаулармен қолданылған. Қазіргі атаумен алғаш рет 1990 жылы пайдаланылды.
DCOP
DCOP мәселесінің негізгі құрамдас бөліктері агенттер мен айнымалылар болып табылады. Маңыздысы, әрбір айнымалы агенттің меншігінде болады; осы себепті мәселе үлестірілген болып табылады. Формальды түрде, DCOP – бұл топтама, онда: – агенттер жиынтығы, – айнымалылар жиынтығы, – айнымалылар домендерінің жиынтығы, , мұндағы әрқайсысы айнымалының мүмкін мәндерін қамтитын шекті жиынтық. Егер тек екі мәнді (мысалы, 0 немесе 1) қамтитын болса, онда ол екілік айнымалы деп аталады. – бұл құн функциясы. Бұл функция әрбір мүмкін жартылай тапсырманы құнға бейімдейді. Әдетте, тек бірнеше мәні ғана нөлден өзгеше болады және ол нөлден өзгеше мән берілген топтамалар тізімі түрінде көрсетіледі. Осындай әрбір топтама шектеу деп аталады. Бұл жиынтықтағы әрбір шектеу – айнымалылардың әрбір мүмкін берілуіне нақты мән тағайындайтын функция. Кейбір арнайы шектеу түрлері: Бірлік шектеулер – бір айнымалыға қатысты шектеулер, яғни, кейбір үшін. Екілік шектеулер – екі айнымалыға қатысты шектеулер, яғни, кейбір үшін. – меншік функциясы. Бұл функция әрбір айнымалыны оған байланысты агентке бейімдейді. Бұл агенттің айнымалының мәнін тағайындау жауапкершілігін білдіреді. міндетті түрде инъекция емес, яғни, бір агент бірнеше айнымалыға ие болуы мүмкін. Сондай-ақ, міндетті түрде сюръекция емес, яғни, кейбір агенттерге ешқандай айнымалылар тиесілі болмауы мүмкін. – мақсаттық функция. Бұл оператор барлық мүмкін айнымалы тапсырмалары үшін барлық жеке құндарды жинақтайды. Бұл әдетте қосу арқылы жүзеге асырылады:
is the set of agents, is the set of variables, is the set of variable domains, <math>\{D 1, D 2, \dots, D { where each is a finite set containing the possible values of variable If contains only two values (e. g. 0 or 1), then is called a binary variable. is the cost function. It is a function that maps every possible partial assignment to a cost. Usually, only few values of are non zero, and it is represented as a list of the tuples that are assigned a non zero value. Each such tuple is called a constraint. Each constraint in this set is a function assigning a real value to each possible assignment of the variables. Some special kinds of constraints are:
Unary constraints constraints on a single variable, i. e., for some Binary constraints constraints on two variables, i. e, for some is the ownership function. It is a function mapping each variable to its associated agent. means that variable "belongs" to agent This implies that it is agent 's responsibility to assign the value of variable Note that is not necessarily an injection, i. e., one agent may own more than one variables. It is also not necessarily a surjection, i. e., some agents may own no variables. is the objective function. It is an operator that aggregates all of the individual costs for all possible variable assignments. This is usually accomplished through summation:
DCOP-тың мақсаты – әрбір агентке байланысты айнымалыларға мәндерді тағайындау, осылайша айнымалылардың берілген тапсырмасы үшін құнды азайту немесе арттыру.
Тапсырмалар
Құнды тағайындау – доменнің элементі болатын жұп. Ішінара тағайындау – әрқайсысы ең көп дегенде бір рет кездесетін құнды тағайындаулар жиынтығы. Оны контекст деп те атайды. Бұл DCOP-тағы айнымалыларды олардың ағымдағы мәндеріне бейнелейтін функция ретінде қарастырылуы мүмкін: контекст – негізінен ішінара шешім болып табылады және мәселенің барлық айнымалыларының мәндерін қамтуы міндетті емес; сондықтан агент әлі айнымалыға мән тағайындамаған. Осы бейнелеуді ескере отырып, f функциясының «доменін» (яғни кіріс мәндерінің жиынтығын) DCOP үшін барлық мүмкін контекстер жиынтығы ретінде қарастыруға болады. Сондықтан, осы мақаланың қалған бөлігінде біз контекст ұғымын (яғни функция) f функциясының кірісі ретінде қолдануымыз мүмкін. Толық тағайындау – әрқайсысы дәл бір рет кездесетін тағайындау, яғни барлық айнымалыларға мән тағайындалған. Оны DCOP-қа шешім деп те атайды. Оптималды шешім – бұл мақсатты функция оңтайландырылған (яғни, проблема түріне байланысты максимизацияланған немесе минималдаған) толық тағайындау.
A partial assignment is a set of value assignments where each appears at most once. It is also called a context. This can be thought of as a function mapping variables in the DCOP to their current values:
Note that a context is essentially a partial solution and need not contain values for every variable in the problem; therefore, implies that the agent has not yet assigned a value to variable Given this representation, the "domain" (that is, the set of input values) of the function f can be thought of as the set of all possible contexts for the DCOP. Therefore, in the remainder of this article we may use the notion of a context (i. e., the function) as an input to the function. A full assignment is an assignment in which each appears exactly once, that is, all variables are assigned. It is also called a solution to the DCOP. An optimal solution is a full assignment in which the objective function is optimized (i. e., maximized or minimized, depending on the type of problem).
Мәселелердің мысалы
Әртүрлі салалардан туындаған түрлі мәселелер DCOP ретінде берілуі мүмкін.
Таратылған графикті бояулау
Графты түске бояу мәселесі мынадай: берілген граф және түстер жиыны бойынша, әр төбеге , түс тағайындаңыз , сонда қатар орналасқан бір түстің төбелерінің саны ең аз болады. DCOP ретінде, әр төбеге байланысты түсті таңдау үшін бір агент тағайындалған. Әрбір агенттің бір ғана айнымалысы бар, оның доменінің кардиналдылығы (әр мүмкін түс үшін бір домендік мән бар). Әрбір төбе үшін , доменімен бір айнымалы бар . Әрбір қатар орналасқан төбелер жұбы үшін, егер екі байланысты айнымалыға бірдей түс тағайындалса, 1 құндылықтағы шектеу бар: Мақсат, содан кейін, ең аз мәнді табу.
Бірнеше рюкзакты бөлу мәселесі
Рюкзак проблемасының үлестірілген көптеген нұсқасы былай қойылады: әр түрлі көлемдегі заттар жиынтығы және әр түрлі сыйымдылықтағы рюкзактар жиынтығы берілгенде, әр затты рюкзакқа тағайындау керек, сонда артық көлемнің мөлшері ең аз болады. Егде, заттар жиынтығы болсын, рюкзактар жиынтығы болсын, заттарды олардың көлеміне бейімдейтін функция болсын, ал рюкзактарды олардың сыйымдылығына бейімдейтін функция болсын. Бұл мәселені DCOP ретінде кодтау үшін, әрбір үшін бір айнымалы жасаңыз, оған сәйкес доменімен. Содан кейін, барлық мүмкін контекстер үшін: мұнда контекст рюкзаққа тағайындалған жалпы салмақты білдіреді:
Таратылған элементтерді бөлу мәселесі
Нысанды бөлу мәселесі мынадай. Бірнеше агенттер арасында бөлінетін бірнеше нысан бар. Әр агенттің нысандарға берілетін бағасы әртүрлі. Мақсат – жаһандық мақсатты оңтайландыру, мысалы, пайдалылықтардың қосындысын максималдау немесе қызғанышты азайту. Нысанды бөлу мәселесі DCOP ретінде келесідей құрастырылуы мүмкін. Әр агент i және нысан j үшін екілік айнымалы vij қосыңыз. Айнамалының мәні "1", егер агент нысанды алса, әйтпесе "0". Айнамалы i агентке тиесілі. Әр нысанның ең көп дегенде бір агентке берілуін қамтамасыз ету үшін, бір нысанға қатысты әр екі түрлі айнымалы үшін екілік шектеулер қосыңыз: егер екі айнымалы бір уақытта "1" болса, шексіз шығын, әйтпесе – нөлдік шығын. Барлық нысандарды бөлу қажеттігін көрсету үшін, әр нысан үшін n-арлық шектеу қосыңыз (мұнда n – агенттер саны), егер осы нысанға қатысты ешбір айнымалы "1" болмаса, онда шексіз шығын.
ADCOP-ті шешу тәсілдері
ADCOP-ті шешудің қарапайым жолы – әр шектеуді функциялардың қосындысына тең шектеумен алмастыру. Дегенмен, бұл шешім агенттерден олардың қыналы функцияларын ашуды қажет етеді. Көбінесе, бұл жеке құпиялылыққа қатысты мәселелер тудырады. Тағы бір тәсіл – Жеке Оқиғаларды Айнымалылар ретінде қарастыру (PEAV) деп аталады. Бұл тәсілде әрбір айнымалы өзінің айнымалыларынан өзге, шектеу желісіндегі көршілеріне тиесілі барлық айнымалылардың "көшірме айнымалыларына" да ие болады. Көшірме айнымалылардың бастапқы айнымалыларға тең болуын қамтамасыз ететін қосымша шектеулер (шешілмейтін құнымен) бар. Бұл әдістің кемшілігі – айнымалылар мен шектеулердің саны бастапқыдан әлдеқайда көп, бұл есептеу уақытын ұзартуға әкеледі. Үшінші тәсіл – DCOP үшін жасалған қолданыстағы алгоритмдерді ADCOP жүйесіне бейімдеу. Бұл толық іздеу алгоритмдері және жергілікті іздеу алгоритмдері үшін де жасалды. Кепілді жеке пайда: агенттер өздерінің пайдасы кооперациясыз жағдайдағыдан кем болмаса, жалпы игілік үшін әрекет етуге келіседі (яғни, соңғы нәтиже бастапқы жағдайды Парето жақсартуы керек). Ламбда ынтымақтастығы: параметр бар. Агенттер өздерінің пайдасы кооперациясыз пайдасынан кем болмаса, жалпы игілік үшін әрекет етуге келіседі. Мұндай ішінара ынтымақтастық ADCOP-терді шешу үшін ADCOP алгоритмдерін бейімдеу қажет.
Кітаптар мен зерттеулер
Бұл - құрастырылған кітаптың бір тарауы. 1- және 2-тарауларды қараңыз; оны интернеттен тегін жүктеуге болады.