API tools faq
paste
Guest User

Untitled

a guest
Jun 23rd, 2012
153
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.56 KB | None | 0 0
raw download clone embed print report
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4.  
  5. #define POL_VARS (4) // ilość zmiennych wielomianu
  6. #define POL_1 (3) // ilość elementów pierwszego stopnia
  7. #define POL_2 (3) // ilość elementów drugiego stopnia
  8. #define POL_3 (3) // ilość elementów trzeciego stopnia
  9. #define POL_RNG (200) // zakres wartości współczynników wielomianu
  10.  
  11.  
  12. #define DATA_RNG (6.0) // zakres zmiennych wejściowych wielomianu
  13. #define DATA_CNT ((POL_1+POL_2+POL_3)*2) // ilość danych na których będą aproksymowane losowe wielomiany
  14.  
  15.  
  16. #define SYM_CNT (5) // ilość symulacji
  17. #define SYM_ALL_GAMES (2000000000) // ilość turniejów
  18. #define SYM_CNT_PROG (10) // ilość programów w turnieju
  19. #define SYM_PAIR_GAMES (2) // ilość gier dla każdej pary
  20. #define SYM_TOURNS (SYM_ALL_GAMES/(SYM_CNT_PROG*(SYM_CNT_PROG-1)/2*SYM_PAIR_GAMES)) // ilość turniejów
  21. #define SYM_RAND1 (4.00) // zaburzenia stałe
  22. #define SYM_RAND2 (0.00) // zaburzenia procentowe
  23. #define SYM_STEP_START (0.0001) // krok uczący
  24. #define SYM_STEP_END (0.0001) // krok uczący
  25.  
  26.  
  27. #define CHAOS (0.10) // chaos dodawany do parametrów przed rozgrywką
  28.  
  29.  
  30. struct VarPoly {
  31. int pol1[POL_1>0?POL_1:1];
  32. int pol2[POL_2>0?POL_2:1];
  33. int pol3[POL_3>0?POL_3:1];
  34. };
  35.  
  36. // wielomian
  37. struct Pol {
  38. double pol1[POL_1>0?POL_1:1];
  39. double pol2[POL_2>0?POL_2:1];
  40. double pol3[POL_3>0?POL_3:1];
  41. };
  42.  
  43. struct Data {
  44. double x[POL_VARS]; // wejście
  45. double y; // wyjście
  46. };
  47.  
  48. double frand() {
  49. double r = rand() % 1024;
  50. r *= 1024;
  51. r += rand() % 1024;
  52. return r / 1024.0 / 1024.0;
  53. }
  54.  
  55. void randVar( VarPoly &var_pol ) {
  56.  
  57. for( int i=0 ; i<POL_1 ; i++ ) {
  58. var_pol.pol1[i] = rand() % POL_VARS;
  59. for( int j=0 ; j<i ; j++ ) {
  60. if( var_pol.pol1[j] == var_pol.pol1[i] ) {
  61. i--;
  62. break;
  63. }
  64. }
  65. }
  66.  
  67. for( int i=0 ; i<POL_2 ; i++ ) {
  68. var_pol.pol2[i] = rand() % POL_VARS;
  69. var_pol.pol2[i] = rand() % POL_VARS;
  70. for( int j=0 ; j<i ; j++ ) {
  71. if( var_pol.pol2[j] == var_pol.pol2[i] && var_pol.pol2[j] == var_pol.pol2[i] ) {
  72. i--;
  73. break;
  74. }
  75. }
  76. }
  77.  
  78. for( int i=0 ; i<POL_3 ; i++ ) {
  79. var_pol.pol3[i] = rand() % POL_VARS;
  80. var_pol.pol3[i] = rand() % POL_VARS;
  81. var_pol.pol3[i] = rand() % POL_VARS;
  82. for( int j=0 ; j<i ; j++ ) {
  83. if( var_pol.pol3[j] == var_pol.pol3[i] && var_pol.pol3[j] == var_pol.pol3[i] && var_pol.pol3[j] == var_pol.pol3[i] ) {
  84. i--;
  85. break;
  86. }
  87. }
  88. }
  89.  
  90. }
  91.  
  92. // tworzymy zupełnie losowy wielomian
  93. void randPol( Pol &pol ) {
  94. for( int i=0 ; i<POL_1 ; i++ ) pol.pol1[i] = frand() * POL_RNG * 2 - POL_RNG;
  95. for( int i=0 ; i<POL_2 ; i++ ) pol.pol2[i] = frand() * POL_RNG * 2 - POL_RNG;
  96. for( int i=0 ; i<POL_3 ; i++ ) pol.pol3[i] = frand() * POL_RNG * 2 - POL_RNG;
  97. }
  98.  
  99.  
  100. // tworzymy losowy wielomian w pobliżu wielomianu bazowego
  101. void randomNear( Pol &pol , const Pol &base ) {
  102. pol = base;
  103. for( int i=0 ; i<POL_1 ; i++ ) pol.pol1[i] += fabs( pol.pol1[i] ) * ( frand() * SYM_RAND2 * 2 - SYM_RAND2 ) + frand() * SYM_RAND1 * 2 - SYM_RAND1;
  104. for( int i=0 ; i<POL_2 ; i++ ) pol.pol2[i] += fabs( pol.pol2[i] ) * ( frand() * SYM_RAND2 * 2 - SYM_RAND2 ) + frand() * SYM_RAND1 * 2 - SYM_RAND1;
  105. for( int i=0 ; i<POL_3 ; i++ ) pol.pol3[i] += fabs( pol.pol3[i] ) * ( frand() * SYM_RAND2 * 2 - SYM_RAND2 ) + frand() * SYM_RAND1 * 2 - SYM_RAND1;
  106. }
  107.  
  108.  
  109. // obliczamy wartość wielomianu
  110. double computePol( const double x[POL_VARS] , const VarPoly &var , const Pol &pol ) {
  111. double y = 0;
  112. for( int i=0 ; i<POL_1 ; i++ ) y += pol.pol1[i] * x[ var.pol1[i] ];
  113. for( int i=0 ; i<POL_2 ; i++ ) y += pol.pol2[i] * x[ var.pol2[i] ] * x[ var.pol2[i] ];
  114. for( int i=0 ; i<POL_3 ; i++ ) y += pol.pol3[i] * x[ var.pol3[i] ] * x[ var.pol3[i] ] * x[ var.pol3[i] ];
  115. return y;
  116. }
  117.  
  118. // obliczamy błąd wielomianu
  119. double errorPol( const Data data[DATA_CNT] , const VarPoly &var , const Pol &pol ) {
  120. double er = 0;
  121. for( int i=0 ; i<DATA_CNT ; i++ ) {
  122. const double tmp = computePol( data[i].x , var , pol ) - data[i].y;
  123. er += tmp * tmp;
  124. }
  125. return sqrt( er / DATA_CNT );
  126. }
  127.  
  128. // tworzymy losowe dane, tak aby były zgodne z wielomianem. w
  129. // ten sposób uzyskujemy wielomian idealnie zaproksymowany.
  130. void makeData( Data data[DATA_CNT] , const VarPoly &var , const Pol &pol ) {
  131. for( int i=0 ; i<DATA_CNT ; i++ ) {
  132. for( int j=0 ; j<POL_VARS ; j++ )
  133. data[i].x[j] = frand() * DATA_RNG * 2 - DATA_RNG;
  134. data[i].y = computePol( data[i].x , var , pol );
  135. }
  136. }
  137.  
  138. static unsigned int cnt_games = 0;
  139. // wyłaniamy wielomian zwycięski
  140. int tournament( const Data data[DATA_CNT] , const VarPoly &var , const Pol pol[SYM_CNT_PROG] ) {
  141. int res[SYM_CNT_PROG];
  142.  
  143. for( int i=0 ; i<SYM_CNT_PROG ; i++ )
  144. res[i] = 0;
  145.  
  146. for( int i=0 ; i<SYM_CNT_PROG-1 ; i++ ) {
  147. for( int j=i+1 ; j<SYM_CNT_PROG ; j++ ) {
  148. for( int k=0 ; k<SYM_PAIR_GAMES ; k++ ) {
  149. Pol pol1 = pol[i];
  150. Pol pol2 = pol[j];
  151.  
  152. for( int l=0 ; l<POL_1 ; l++ ) { pol1.pol1[l] += pol1.pol1[l] * (frand() * CHAOS * 2 - CHAOS); pol2.pol1[l] += pol2.pol1[l] * (frand() * CHAOS * 2 - CHAOS); }
  153. for( int l=0 ; l<POL_2 ; l++ ) { pol1.pol2[l] += pol1.pol2[l] * (frand() * CHAOS * 2 - CHAOS); pol2.pol2[l] += pol2.pol2[l] * (frand() * CHAOS * 2 - CHAOS); }
  154. for( int l=0 ; l<POL_3 ; l++ ) { pol1.pol3[l] += pol1.pol3[l] * (frand() * CHAOS * 2 - CHAOS); pol2.pol3[l] += pol2.pol3[l] * (frand() * CHAOS * 2 - CHAOS); }
  155.  
  156. const double val1 = errorPol( data , var , pol1 );
  157. const double val2 = errorPol( data , var , pol2 );
  158.  
  159. if( val1 < val2 ) res[i] += 2;
  160. else if( val2 < val1 ) res[j] += 2;
  161. else { res[i] += 1; res[j] += 1; }
  162.  
  163. cnt_games ++ ;
  164.  
  165. }}}
  166.  
  167. int max = 0;
  168. for( int i=1 ; i<SYM_CNT_PROG ; i++ )
  169. if( res[max] < res[i] )
  170. max = i;
  171.  
  172. return max;
  173. }
  174.  
  175.  
  176. // uczymy przez przesunięcie wielomianu bazowego do zwycięskiego
  177. void learnBase( Pol &base , const Pol &win , const double step ) {
  178. for( int i=0 ; i<POL_1 ; i++ ) base.pol1[i] += ( win.pol1[i] - base.pol1[i] ) * step;
  179. for( int i=0 ; i<POL_2 ; i++ ) base.pol2[i] += ( win.pol2[i] - base.pol2[i] ) * step;
  180. for( int i=0 ; i<POL_3 ; i++ ) base.pol3[i] += ( win.pol3[i] - base.pol3[i] ) * step;
  181. }
  182.  
  183. // odległość pomiędzy dwoma rozwiązaniami
  184. double distPol( const Pol &pol1 , const Pol &pol2 ) {
  185. double dist = 0;
  186. for( int i=0 ; i<POL_1 ; i++ ) dist += ( pol1.pol1[i] - pol2.pol1[i] ) * ( pol1.pol1[i] - pol2.pol1[i] );
  187. for( int i=0 ; i<POL_2 ; i++ ) dist += ( pol1.pol2[i] - pol2.pol2[i] ) * ( pol1.pol2[i] - pol2.pol2[i] );
  188. for( int i=0 ; i<POL_3 ; i++ ) dist += ( pol1.pol3[i] - pol2.pol3[i] ) * ( pol1.pol3[i] - pol2.pol3[i] );
  189. return sqrt( dist / (POL_1+POL_2+POL_3) );
  190. }
  191.  
  192.  
  193. double learnSym( const Data data[DATA_CNT] , const VarPoly &var , Pol &base , const Pol &best ) {
  194. printf("start %10.4lf %10.4lf %10.4lf\n", errorPol(data,var,base) , distPol(base,best) , errorPol(data,var,best) );
  195. fflush(stdout);
  196. double step = SYM_STEP_START;
  197. const double fade = pow( SYM_STEP_END/SYM_STEP_START , 1.0 / ( SYM_TOURNS - 1.0 ) );
  198. for( int i=0 ; i < SYM_TOURNS ; i++ ) {
  199. Pol progs[SYM_CNT_PROG];
  200. for( int j=0 ; j<SYM_CNT_PROG ; j++ )
  201. randomNear( progs[j] , base );
  202. const int win = tournament( data , var , progs );
  203. learnBase( base , progs[win] , step );
  204. if( i%10000 == 0) {
  205. printf("%.2lf %lf %lf\n", cnt_games/1000000.0 , errorPol(data,var,base) , distPol(base,best) );
  206. fflush(stdout);
  207. }
  208. step *= fade;
  209. }
  210. printf("end %10.4lf %10.4lf %10.4lf\n" , errorPol(data,var,base) , distPol(base,best) , step/fade );
  211. fflush(stdout);
  212. return errorPol(data,var,base);
  213. }
  214.  
  215. unsigned long long seeds[] = {0x4FF12B4EEC03E700ULL, 0x57E6398A9A8B2211ULL, 0xB4615E9685F2E8C3ULL, 0x022F867DF087C9E6ULL, 0xA03563B9C243B8EFULL, 0x5FC7323AF7033998ULL, 0x30823328BAC9CE98ULL, 0x573D9C22D4502AAEULL, 0xDED29242FE519A8BULL, 0x19AE2C4DEF0BC015ULL, 0x1C1CC71A3EB3A4A1ULL, 0xEEC970FC319CFC1FULL, 0x528D055C3D49DA99ULL, 0x1741B598B3F6109BULL, 0x28D335B91AEA7F39ULL, 0xDEDDAD64D3D95FF4ULL, 0xAA3C089F12C25F19ULL, 0xC539DC621B4D0606ULL, 0x9F2AC28AC4737A16ULL, 0xB72DAB1C2F4F590CULL, 0xB271B5F30AD8962EULL, 0xE5B30FCF64399ECEULL, 0x748A6AF8D0AE84BAULL, 0xC4AB1BC380199A5AULL, 0x8EDD48734A9EAE33ULL, 0xC36CF389A2E5192BULL, 0x42BA73766378DF33ULL, 0x469662938753D3DEULL, 0xE970C2AF0F7927C1ULL, 0xBD7A23F4323E674EULL, 0xD829F9FC6BB983C9ULL, 0xBDEA784DB2D7E5B4ULL, 0xD4C4B06BAE93256BULL, 0xEB544E6E115E722CULL, 0xEA47168DADE23E4BULL, 0xC8BB649C22785FB8ULL, 0xBF53BC7FE55202E0ULL, 0xDFC89D57F776F9BBULL, 0x816A616E35380CC6ULL, 0x632E6BAAA6E915DDULL, 0x78ACA5D7424B28A9ULL, 0x80CF3CA43095C9D5ULL, 0x9BAB2DEFB47A99FCULL, 0xEC65A533A95BC5B8ULL, 0x340F702E2FFAC876ULL, 0x88EE4367DDC6C0C1ULL, 0x6F1A7414008F85C6ULL, 0xCAF21613FCB05677ULL, 0x5DF1C1DD328C861BULL, 0xBFC94418AE2CBBF2ULL, 0x2C7D71B3A5AACF75ULL, 0x44FEDB5C8DAC34D8ULL, 0xDD6E940D0EC37EFCULL, 0x4A811353B367B2C7ULL, 0x486CCADEDA12BE85ULL, 0x01A1157CC0E7773FULL, 0xECF76F3947EF30A7ULL, 0xA9CB41DC150433B5ULL, 0xC9D1962CF2F0CB79ULL, 0x6C97F08D41EE92BAULL, 0xFBEAE85B9913C397ULL, 0xC12C6A8813EB33B1ULL, 0xBF3618CBAB212896ULL, 0xC5251C97FE1A8D1AULL};
  216.  
  217. int main(int argc, char *argv[]) {
  218. double sum_error = 0;
  219.  
  220. for( int i=0 ; i<SYM_CNT ; i++ ) {
  221.  
  222. Data data[DATA_CNT];
  223. VarPoly var;
  224. Pol best,base;
  225.  
  226. if( i >= sizeof(seeds)/sizeof(seeds[0]) )
  227. abort();
  228.  
  229. srand( seeds[i] );
  230.  
  231. randPol( best );
  232. randPol( base );
  233. randVar( var );
  234. makeData( data ,var, best );
  235. sum_error += learnSym( data , var , base , best );
  236. }
  237.  
  238. printf("%9d %2d %6.4lf %6.4lf %6.4lf %6.4lf %10.4lf\n" , SYM_ALL_GAMES , SYM_CNT_PROG , SYM_RAND1 , SYM_RAND2 , SYM_STEP_START , SYM_STEP_END , sum_error/SYM_CNT );
  239.  
  240. return 0;
  241. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!