E-book details

Wieloagentowe systemy decyzyjne

Wieloagentowe systemy decyzyjne

Piotr Pałka

Ebook

Niniejsze opracowanie powstało z myślą o odbiorcy zainteresowanym pogłębieniem wiedzy dotyczącej problematyki, projektowania i implementacji
systemów podejmowania decyzji, realizowanych jako systemy wieloagentowe.
Podręcznik jest skierowany do szeroko rozumianego odbiorcy akademickiego, w szczególności do studentów i doktorantów kierunku informatyka, ale także do naukowców zainteresowanych pogłębieniem swojej wiedzy. Zakładam, że czytelnikiem tego podręcznika będą przede wszystkim informatycy, ale jego treść może zainteresować także matematyków czy ekonomistów oraz osoby zainteresowane rozwiązywaniem problemów za pomocą narzędzi informatycznych.
Opisywane w podręczniku przykłady dotyczą praktycznych zastosowań wieloagentowych systemów decyzyjnych w energetyce, geodezji, polityce czy zarządzaniu.

1 Wprowadzenie 13

1.1 Rys historyczny13

1.2 Dzisiejsza rzeczywistość 14

1.3 Układ pracy15

2 Podstawowe pojęcia 17

2.1 Aktor 17

2.2 Aktywny obiekt 17

2.3 Aktywny komponent 18

2.4 Agent 18

2.5 System agentowy 20

2.6 System wieloagentowy 20

2.7 Modele oparte na agentach (ang.agent-based models) 21

2.8 Model Belief-Desire-Intention 21

2.9 Holon 22

2.10 Różnice 22

2.11 Podsumowanie 23

I Tworzenie systemów wieloagentowych 25

3 Komunikacja 27

3.1 Komunikat 27

3.2 Teoria aktów mowy 28

3.2.1 Akt mowy (lingwistycznie) 28

3.2.2 Performatywa 29

3.3 Struktura wiadomości 30

3.4 Języki komunikacji agentów 31

3.4.1 FIPA 31

3.4.2 Język komunikacji FIPA-ACL 33

3.4.3 Struktura wiadomości wg FIPA 34

3.5 Języki treści 35

3.5.1 Sposoby przekazywania treści 35

3.6 Akty komunikacyjne 39

3.7 Protokoły interakcji 42

3.8 Podsumowanie 44

4 Metody służące do projektowania systemów agentowych 45

4.1 Prometheus 46

4.1.1 Specyfikacja systemu 47

4.1.2 Projektowanie architektoniczne 48

4.1.3 Projektowanie szczegółowe 49

4.1.4 Diagramy 49

4.2 Gaia 51

4.2.1 Faza analizy 53

4.2.2 Faza projektowania 62

4.3 AUML 66

4.3.1 Diagram protokołu 66

4.3.2 Konektory 67

4.3.3 Zagnieżdżona i przeplatana interakcja 67

4.3.4 Rozszerzone znaczenie komunikatów 69

4.4 AML 70

4.4.1 Semi-encje AML 70

4.4.2 Encje AML 71

4.4.3 Modelowanie aspektów społecznych systemu wielo­agentowego 72

4.4.4 Modelowanie interakcji 74

4.4.5 Modelowanie zachowań i zdolności 77

4.5 Tropos 78

4.5.1 Modelowanie aktora 80

4.5.2 Modelowanie zależności 80

4.5.3 Modelowanie celów 80

4.5.4 Modelowanie planów 81

4.5.5 Modelowanie zdolności 81

4.5.6 Graficzna reprezentacja modelu 81

4.6 Podsumowanie 81

5 Platformy i języki agentowe

5.1 Platformy agentowe ogólnego zastosowania 83

5.1.1 Java Agent Development framework 83

5.1.2 SPADE 99

5.1.3 Eve 102

5.2 Platformy i języki w podejściu BDI 104

5.2.1 JACK Inteligent Agents 104

5.2.2 Jadex 106

5.2.3 Jason 107

5.3 Platformy symulacyjne 108

5.3.1 GAMA: agent-based, spatially explicit, modeling and simulation platform 108

5.3.2 NetLogo 110

5.3.3 Repast 111

5.4 Język SARL i platforma holoniczna Janus 111

5.4.1 SARL 111

5.4.2 Janus 115

5.5 Podsumowanie 115

II Zastosowanie systemów wieloagentowyc

6 Komercyjne aplikacje agentowe 119

6.1 Telecom Italia Group 119

6.2 Agent Oriented Software Pty. Ltd. 120

6.2.1 Rational Information Broker 120

6.2.2 Wsparcie dla handlu ropą naftową i zarządzaniem operacyjnym 121

6.2.3 Surveillance Agent 121

6.3 Magenta Technology 122

6.4 Whitestein Technologies AG 123

6.5 Eurobios 124

7 Aplikacje agentowe w projektach niekomercyjnych 125

7.1 Aplikacje służące do układania planów 125

7.2 Wsparcie transportu 126

7.3 Wieloagentowa platforma handlowa 126

7.3.1 Koncepcja wieloagentowej platformy wymiany towa­rowej 127

7.3.2 Struktura agentów 128

7.3.3 Mechanizm ofertowania 129

7.3.4 Komunikacja międzyagentowa 129

7.3.5 Protokół wymiany komunikatów 129

7.3.6 Język komunikacji agentów 131

7.4 Handel na rynku pozwoleniami na emisję gazów cieplarnianych132

7.4.1 Role agentów i ich opis 132

7.4.2 Implementacja w JADE 134

7.5 Carpooling w warszawskim Mordorze 136

7.5.1 Warszawski Mordor 136

7.5.2 Agentork 138

7.5.3 Model przejść agenta 139

7.5.4 Wyniki testów 141

7.6 Bilansowanie niedoborów i nadmiarów energii w mikrosieci 145

7.6.1 Podział urządzeń w systemie 145

7.6.2 Role agentów 147

7.6.3 Diagram konwersacji systemu 148

7.6.4 Diagram choreografii dla systemu 149

7.6.5 Diagram kolaboracji 150

7.6.6 Implementacja i przykładowe wyniki testów 151

III Algorytmy wspomagania decyzji w systemach wielo­agentowych 153

8 Algorytmy stosowane w systemach wieloagentowych 155

8.1 Rozproszone spełnianie ograniczeń 156

8.1.1 Problem spełniania ograniczeń 156

8.1.2 Algorytm z nawrotami 158

8.1.3 Rozproszony problem spełniania ograniczeń 160

8.1.4 Asynchroniczny algorytm z nawrotami (ang. asyn­chronous backtracking) 161

8.1.5 Zastosowania 165

8.2 Algorytmy aukcyjne 166

8.2.1 Problem przydziału – problem liniowy 166

8.2.2 Zadanie szeregowania – problem całkowito liczbowo­ liniowy mieszany 171

8.3 Protokół tworzenia sieci kontraktów (ang. Contract Net Pro­tocol) 175

8.3.1 Etapy protokołu 175

8.3.2 Tworzenie sieci wykonawców 176

8.3.3 Wykorzystanie w procesach handlowych 177

8.3.4 Zastosowania 178

8.4 Algorytmy inteligencji stadnej 178

8.4.1 Samoorganizacja społeczności 180

8.4.2 Algorytm kolonii mrówek (ang. ant colony optimization) 180

8.4.3 Algorytm pszczelej kolonii (ang. artificial bee colony) 181

8.4.4 Algorytm szarego wilka (ang. gray wolf optimizer) 183

8.4.5 Model boida 184

8.4.6 Metoda roju cząstek (ang. particle swarm optimization) 185

8.4.7 Zastosowania 187

8.5 Podsumowanie 187

9 Wspomaganie decyzji przy wykorzystaniu agentów 189

9.1 Preferencje i użyteczność 189

9.1.1 Teoria preferencji 189

9.1.2 Funkcja użyteczności 192

9.2 Negocjacje 193

9.2.1 Wybrane protokoły prowadzenia negocjacji 194

9.2.2 Rodzaje ustępstw w negocjacjach wielostronnych 195

9.2.3 Strategie negocjacyjne 196

9.2.4 Zastosowanie negocjacji 198

9.3 Głosowanie 198

9.3.1 Głosowanie większościowe 199

9.3.2 Kryterium Condorceta 199

9.3.3 Głosowanie kumulatywne 200

9.3.4 Głosowanie aprobujące 200

9.3.5 Głosowanie większościowe z eliminacją 200

9.3.6 Głosowanie Bordy 200

9.3.7 Głosowanie Nansona 200

9.3.8 Kryterium Smitha 201

9.3.9 Głosowanie metodą Shulzego 201

9.3.10 Zastosowania 202

9.4 Gry niekooperacyjne 202

9.4.1 Postacie gier 203

9.4.2 Gry przeciwko naturze 205

9.4.3 Gry dwuosobowe 208

9.4.4 Gra o sumienie zerowej 210

9.4.5 Rozwiązanie gry 213

9.4.6 Zastosowania 215

9.5 Gry kooperacyjne 215

9.5.1 Formowanie koalicji 217

9.5.2 Przeszukiwanie grafu struktur koalicji 218

9.5.3 Wybrane własności gier koalicyjnych 219

9.5.4 Rozdział wartości wewnątrz wielkiej koalicji 220

9.5.5 Rdzeń 221

9.5.6 Zastosowania 224

9.6 Programowanie zorientowane rynkowo 224

9.6.1 Model danych rynkowych M3 225

9.6.2 Złożoność towarów wyrażanych w ofertach handlu wielotowarowego 227

9.6.3 Programowanie zorientowane rynkowo z dodatkowy­mi ograniczeniami 229

9.6.4 Zastosowania 230

9.7 Mechanizmy rynkowe 230

9.7.1 Teoria mechanizmów rynkowych 231

9.7.2 Wybrane własności mechanizmu 233

9.7.3 Zastosowania 235

9.8 Podsumowanie 236

10 Podsumowanie 237

Skorowidz 238

Spis rysunków 242

Spis tabel 246

Bibliografia 248