Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгоритми навчання з підкріпленням
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра електронних обчислювальних машин
Інформація про роботу
Рік:
2013
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра електронних
обчислювальних машин
Звіт
про виконання лабораторної роботи № 4
з курсу „ Теорія колективної поведінки інтелектуальних систем ”
Тема:
Алгоритми навчання з підкріпленням
Мета: Реалізувати вказані алгоритми навчання з підкріпленням та дослідити їх поведінку.
Загальні відомості
Розглядаються два алгоритми навчання з підкріпленням (reinforcement learning).
1. Жадібний алгоритм RL (greedy RL).
Для кожної дії a на кожному кроці визначається її вага
Qt(a) = sa / ka, де
t – номер часового кроку,
ka – кількість реалізацій дії a (скільки разів дія a була обрана до моменту часу t),
sa – сумарний виграш, отриманий завдяки реалізації дії a.
[1.0. Перша дія обирається випадково.]
1.1. Реалізувати обрану дію.
1.2. Отримати відгук середовища (виграш/програш).
1.3. Для всіх дій підрахувати значення Qt(a).
1.4. Обрати дію ai, для якої Qt(ai) = max Qt(a), перейти до п.2.1.
2. (-жадібний алгоритм RL ((-greedy RL).
[2.0. Перша дія обирається випадково.]
2.1. Реалізувати обрану дію.
2.2. Отримати відгук середовища (виграш/програш).
2.3. Для всіх дій підрахувати значення Qt(a).
2.4. З ймовірністю (1-() обрати та реалізувати дію ai, для якої Qt(ai) = max Qt(a).
2.5. З ймовірністю ( обрати дію рівновипадково, перейти до п.3.1.
В процесі взаємодії алгоритму RL з середовищем визначаються три залежності:
Залежність біжучого виграшу від часу: R(t).
Залежність біжучого сумарного виграшу від часу: R((t) = (Rt.
Залежність біжучого проценту виграшних дій від часу (середнє значення виграшу, що припадає на одну дію): Ps(t) = (Rt / t.
Завдання
1. Скласти програму наступного змісту (алгоритм роботи програми):
Вибрати тип середовища (env_model)
Ініціалізувати середовище (випадкова ініціалізація)
Вибрати алгоритм навчання з підкріпленням.
Відкрити файл для збереження результатів
Цикл від 1 до T (індекс t)
Отримати код дії, яку обрав алгоритм навчання з підкріпленням
Отримати відгук середовища на цю дію (біжучий виграш)
Модифікувати значення сумарного виграшу
Модифікувати значення проценту виграшних (правильних) дій
Запам’ятати отриманні значення у файлі результатів
Перейти на п.4
Закрити файл результатів.
2. Реалізувати два алгоритми навчання з підкріпленням:
2.1. Жадібний алгоритм RL (greedy RL).
2.2. (-жадібний алгоритм RL ((-greedy RL).
3. Дослідити поведінку алгоритмів навчання з підкріпленням в кожному з трьох середовищ (статичне детерміноване, динамічне детерміноване, стаціонарне випадкове), отримавши для кожного випадку вказані залежності від часу.
4. Порівняти отримані залежності та зробити висновки.
Текст програми
/* Copyright (c) 2005 alb. All Rights Reserved.
* Computer Engineering Department * Lviv Polytechnic National University
* ===============================================
* Multiagent Systems. Lab work 04.
* Agent design II (simple Reinforcement Learning (RL) methods)
* Here two types of RL algorithms (simple Action-Value Methods) are implemented:
* - greedy RL,
* - epsilon greedy RL.
* With given
* set of available actions D={1,2} and
* set of possible responses R={0,1}
* 1 -> reward (win)
* 0 -> punishment (loss)
* you must investigate behaviour of these RL algorithms
* over T interaction in specified environments. */
#include "stdafx.h"
#define NACTION 3
int t; // current time step
int T = 100; // maximum number of time steps (interactions with environment)
int env_model; // environmetn code:
// 1 - envoronment with static response
// 2 - envoronment with predetermined dynamic response
// 3 - envoronment with stationary random response:
// binary bandit task (n-armed bandit, n=2)
// variables for environment's parameters
int env1; // winning action code (env_model = 1)
int env2_action1; // first winning action code (env_model = 2)
int env2_action2; // second winning action code (env_model = 2)
int max_period=6; // max period of action repetitions (env_model = 2)
int cd1 = 0; // counter for first action (env_model = 2)
int cd2 = 0; // counter for second action (env_model = 2)
int env2[2]; // periods of action repetitions (env_model = 2)
double env3[2]; // probabilities of rewards for each action (env_model = 3)
// file for saving results
char * res_file_name = "test.dat";
FILE * res_file;
int action; // RL-agent current action
int response; // current response of environment (can be 0 or 1)
double mr = 0; // mean reward
// results
int R = 0; // current reward over time R(t)
int sumR = 0; // total reward over time sumR(t)
float prcR = 0; // success percent(rate) over time prcR(t)
int ag_type = 1; // agent type
int actNumber = NACTION; // action number of automaton
int Sa[NACTION];
int ka[NACTION];
double Qa[NACTION];
double epsilon = 0.1;
int randomChoice (int _n) {
int r;
srand( (unsigned)time( NULL ) );
r = (int) ((float)_n * (float)rand() / (float)RAND_MAX);
return r + 1;
}
// automatic initialization of environment
void env_init (int env_id) {
int i;
int tmp;
switch (env_id) {
case 1: // envoronment with static response
env1 = randomChoice(actNumber);
break;
case 2: // envoronment with predetermined dynamic response
// random choice of first winning action (1 or 2)
if (actNumber == 2) {
env2_action1 = randomChoice(2);
if (env2_action1 == 1) env2_action2 = 2; else env2_action2 = 1;
// random choice of repitition number for first action
tmp = (int) ((float)(max_period - 1) * (float)rand() / (float)RAND_MAX);
env2[0] = tmp + 1;
// random choice of repitition number for second action
tmp = (int) ((float)(max_period - 1) * (float)rand() / (float)RAND_MAX);
env2[1] = tmp + 1;
}
break;
case 3: // envoronment with stationary random response
for(i = 0; i < actNumber; i++) env3[i] = (float)rand() / (float)RAND_MAX;
break;
default: printf("lab4 error: wrong env model code specified\n");
}
}
// response generation
int env_response (int env_id) {
int win_action, _response;
float ftmp;
switch (env_id) {
case 1: // envoronment with static response
if (action == env1) _response = 1;
else _response = 0;
break;
case 2: // envoronment with predetermined dynamic response
if (cd1 < env2[0]) {
cd1 ++;
win_action = env2_action1;
}
else {
if (cd2 < (env2[1] - 1)) {
cd2 ++;
win_action = env2_action2;
}
else {
cd1 = 0;
cd2 = 0;
win_action = env2_action2;
}
}
if (action == win_action) _response = 1;
else _response = 0;
break;
case 3: // envoronment with stationary random response
ftmp = (float)rand() / (float)RAND_MAX;
if (ftmp < env3[action-1]) _response = 1;
else _response = 0;
break;
default: printf("lab1 error: wrong env model code specified\n");
}
return _response;
}
// print environment parameters
void env_info (void) {
int j;
printf("\nenvironment = %d", env_model);
switch (env_model) {
case 1: // envoronment with static response
printf("\n (%d)\n",env1);
break;
case 2: // envoronment with predetermined dynamic response
printf("\n(%d) -> %d, (%d) -> %d\n",env2_action1,env2[0],env2_action2,env2[1]);
break;
case 3: // envoronment with stationary random response
printf("\naction number = %d\n", actNumber);
for(j=0; j<actNumber; j++) printf("(%d) -> %f\n", j + 1, env3[j]);
printf("\n");
break;
default: printf("lab4 error: wrong env model code specified\n");
}
}
void res_open_file (void) {
if ((res_file = fopen(res_file_name,"w")) == NULL) {
fprintf(stderr, "Cannot open file <%s> for experimental results.\n", res_file_name);
}
}
void res_close_file (void) {
fclose(res_file);
}
void res_store_next_string (void) {
fprintf(res_file,"%d,%d,%f\n",R,sumR,prcR);
}
int casual_agent (void) {
return randomChoice(2);
}
int maxQa (void) {
int j;
int mi; // index of maximum Qa
mi = 0;
for (j=1; j<actNumber; j++) if (Qa[j] > Qa[mi]) mi = j;
mi++;
return mi;
}
// greedy RL
int ag_greedy (void) {
int i;
int ca = action - 1; // current action index
if(t==0) {
for(i=0; i<actNumber; i++) {Sa[i] = 1; ka[i] = 1; Qa[i] = 1;}
action = randomChoice(actNumber);
}
else {
Sa[ca] = Sa[ca] + response;
ka[ca]++;
Qa[ca] = (double)Sa[ca] / (double)ka[ca];
action = maxQa();
}
return action;
}
// epsilon greedy RL
int ag_epsilon_greedy (void) {
int i;
int ca = action - 1; // current action index
float rand_num;
if(t==0) {
for(i=0; i<actNumber; i++) {Sa[i] = 1; ka[i] = 1; Qa[i] = 1;}
action = randomChoice(actNumber);
}
else {
Sa[ca] = Sa[ca] + response; ka[ca]++;
Qa[ca] = (double)Sa[ca] / (double)ka[ca];
rand_num = (float)rand() / (float)RAND_MAX;
if (rand_num < epsilon) action = randomChoice(actNumber);
else action = maxQa();
}
return action;
}
// print information about agent
void ag_info (void) {
printf("agent --> ");
switch (ag_type) {
case 1: printf("casual agent"); break;
case 2: printf("RL-agent, Action-Value Method --> greedy"); break;
case 3: printf("RL-agent, Action-Value Method --> epsilon-greedy"); break;
default: printf("lab4 error: wrong <ag_type> value specified\n");
}
printf("\n\n");
}
int main (int argc, char* argv[])
{
int i;
srand((unsigned)time(NULL)); // init random-number generator
env_model = 3; // 1,2 or 3
ag_type = 3; // 1,2,3
// set parameters of chosen environment
env_init(env_model);
if (env_model==3) for(i=0;i<actNumber;i++) mr=mr + (1/(double)actNumber) * env3[i];
res_open_file(); // open file for results
printf("starting...\n\n");
// main cycle of program (over interactions with environment)
for (t=0; t < T; t++) {
switch (ag_type) { // get learning automaton action
case 1: action = casual_agent(); break; // casual
case 2: action = ag_greedy(); break; // greedy
case 3: action = ag_epsilon_greedy(); break; // epsilon-greedy
default: printf("lab4 error: wrong <ag_type> value specified\n");
}
printf("agent action: %d | ", action);
response = env_response(env_model); // get response of environment
printf("env response: %d --> ",response); // print response of environment
// calculate results
R = response;
sumR = sumR + R;
prcR = (float)sumR / ((float)t + 1);
res_store_next_string(); // save current results in file
printf("sum win: %d, rate win: %f\n", sumR, prcR); // print current results
}
printf("\n%d interactions performed\n", t);
env_info(); // print information about environment
if(env_model==3) printf("mean reward is %f\n\n",mr);
ag_info(); // print information about agent
res_close_file(); // close file with results
return 0;
}
Результати
Залежності біжучого проценту виграшних дій від часу (середнє значення виграшу, що припадає на одну дію): Ps(t) = (Rt / t для кожного алгоритму навчання з підкріпленням для стаціонарного випадкового середовища у графічному вигляді із зазначенням чисельних характеристик автоматів та алгоритмів, для яких отримано результати.
Кількість дій, доступних автомату
2
3
жадібний алгоритм RL
environment = 3
action number = 2
(1) -> 0.887326
(2) -> 0.362499
mean reward is 0.624912
environment = 3
action number = 3
(1) -> 0.984191
(2) -> 0.193396
(3) -> 0.270058
mean reward is 0.482548
(-жадібний алгоритм RL
environment = 3
action number = 2
(1) -> 0.895779
(2) -> 0.243812
mean reward is 0.569796
environment = 3
action number = 3
(1) -> 0.999634
(2) -> 0.035768
(3) -> 0.771599
mean reward is 0.602334
автомат з випадковим вибором (casual)
environment = 3
action number = 2
(1) -> 0.871181
(2) -> 0.224006
mean reward is 0.547594
environment = 3
action number = 3
(1) -> 0.994049
(2) -> 0.666921
(3) -> 0.242012
mean reward is 0.634327
Порівняння навчання автоматів з різними тактиками
На графіку подано порівняння трьох типів автоматів(двох автоматів, що навчаються за алгоритмом з підкріпленням і одного, що діє випадково) при їх навчанні у стаціонарному випадковому середовищі:
Доступних дій – 2
Доступних дій – 3
Висновки: виконуючи дану лабораторну роботу я досліджував виконання алгоритмів навчання з підкріпленням – жадібний та (-жадібний алгоритми. (-жадібний алгоритм є модифікацією жадібного алгоритму із внесенням ймовірнісної складової – (, що наближає його до нецілеспрямованої поведінки. Це допомагає (-жадібному алгоритму швидше сприймати та вивчати зміни у середовищі, хоча інколи не дозволяє йому досягти такого високого відсотку виграшів, якого досягає жадібний алгоритм.
Як видно з графіків, «жадібні» алгоритми працюють ефективніше за випадковий.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора