Test avec des opérateurs de variation hétérogène sur le problème du OneMax

Nous définissons ici le nombre d'ile à utiliser ainsi que le niveau de lissage des courbes.


In [2]:
N=4
A=1000
OPS=['bit-flip', '1-flip', '3-flip', '5-flip']

Puis quelques routines…


In [3]:
import pandas as pd

In [4]:
import matplotlib as mpl
mpl.rc('figure', figsize=(10, 8))

In [5]:
%%script /Dev/dim/release/application/OneMax/onemax -h


/Dev/dim/release/application/OneMax/onemax: 

Usage: /Dev/dim/release/application/OneMax/onemax [Options]
Options of the form "-f[=Value]" or "--Name[=value]"
Where:

### GENERAL ########################################################################
-h, --help :	Prints this message (optional, default: 0)
--stopOnUnknownParam :	Stop if unkown param entered (optional, default: 1)
-S, --seed :	Random number seed (optional, default: 0)

### EVOLUTION ENGINE ###############################################################
-P, --popSize :	Population Size (optional, default: 100)

### ISLANDS MODEL ##################################################################
--sync :	sync (optional, default: 1)
--smp :	smp (optional, default: 1)
--nislands :	Number of islands (see --smp) (optional, default: 4)
-a, --alpha :	Alpha Probability (optional, default: 0.2)
-A, --alphaF :	Alpha Fitness (optional, default: 0.01)
-b, --beta :	Beta Probability (optional, default: 0.01)
-d, --probaSame :	Probability for an individual to stay in the same island (optional, default: 25)
-I, --initG :	initG (optional, default: 1)
-U, --update :	update (optional, default: 1)
-F, --feedback :	feedback (optional, default: 1)
-M, --migrate :	migrate (optional, default: 1)
--nmigrations :	Number of migrations to do at each generation (0=all individuals are migrated) (optional, default: 1)
--stepTimer :	stepTimer (milliseconds) (optional, default: 0)
--deltaUpdate :	deltaUpdate (optional, default: 1)
--deltaFeedback :	deltaFeedback (optional, default: 1)
--sensitivity :	sensitivity of delta{t} (1/sensitivity) (optional, default: 1)
--rewardStrategy :	Strategy of rewarding: best or avg (optional, default: best)

### LOGGER #########################################################################
-v, --verbose :	Set the verbose level (optional, default: quiet)
-l, --print-verbose-levels :	Print verbose levels (optional, default: 0)
-o, --output :	Redirect a standard output to a file (optional, default: )

### OUTPUT #########################################################################
--monitorPrefix :	Monitor prefix filenames (optional, default: result)
--printBestStat :	Print Best/avg/stdev every gen. (optional, default: 0)

### PARALLELIZATION ################################################################
--parallelize-dynamic :	Enable dynamic memory shared parallelization (optional, default: 1)
--parallelize-do-measure :	Do some measures during execution (optional, default: 0)

### PARALLELIZATION WITH MPI #######################################################
--parallelize-packet-size :	Number of elements which should be sent in a single message during a parallel evaluation based on message passing. (optional, default: 1)

### PERSISTENCE ####################################################################
-L, --Load :	A save file to restart from (optional, default: )
-r, --recomputeFitness :	Recompute the fitness after re-loading the pop.? (optional, default: 0)
--status :	Status file (optional, default: /Dev/dim/release/application/OneMax/onemax.status)

### PROBLEM ########################################################################
-n, --chromSize :	The length of the bitstrings (optional, default: 1000)

### STOPPING CRITERION #############################################################
-T, --targetFitness :	Stop when fitness reaches (optional, default: 1000)
-G, --maxGen :	Maximum number of generations () = none) (optional, default: 0)
-X, --maxTime :	Maximum time (in seconds) used by the program () = none) (optional, default: 0)

@param_file 	 defines a file where the parameters are stored

You can use an edited copy of file /Dev/dim/release/application/OneMax/onemax.status as parameter file

Paramètres

Nous lançons le test suivant: l'algorithme DIM appliqué au problème du OneMax avec les paramétres:

  • 4 iles avec les opérateurs de variation suivants: bit-flip,1flip,3flip,5flip
  • les solutions sont initialisées à zéro
  • avec un critère d'arrêt « targetFitness » définit à 1000 (pas de genMax)
  • en mode SMP (synchrone)
  • $\alpha_p = 0.2$
  • $\beta_p = 0.01$
  • $\alpha_f = 0.2$
  • statégie de récompense: MAX
  • $P=100$
  • $$M = \begin{bmatrix} 25 & 25 & 25 & 25 \\\ 25 & 25 & 25 & 25 \\\ 25 & 25 & 25 & 25 \\\ 25 & 25 & 25 & 25 \\\ \end{bmatrix}$$

In [7]:
%%script timeout 10 /Dev/dim/release/application/OneMax/onemax --monitorPrefix=/tmp/onemax_test_result --targetFitness=1000 --nislands=4


Migration probability (in %) among islands
	0	1	2	3
0	25	25	25	25
1	25	25	25	25
2	25	25	25	25
3	25	25	25	25

sum	100	100	100	100
island 0
4 0
island 1
4 1
island 2
4 2
island 3
4 3
end

In [8]:
!tail /tmp/onemax_test_result_monitor_*


==> /tmp/onemax_test_result_monitor_0 <==
0,7.44,2013-Jul-11 17:12:19.728011,5045,1,0,0,999,1,999,1,1,0.7,96,1.2,2.1,100,0,5.27148e-10,0.00430968,1.11818e-19,7.34647e-16,0,1,0,0
0,7.441,2013-Jul-11 17:12:19.729406,5046,5,0,0,995,1,998,5,1,0.7,96.1,1.2,2,100,0,5.21876e-10,0.00426658,1.10699e-19,7.27301e-16,0,1,0,0
0,7.443,2013-Jul-11 17:12:19.730816,5047,6,0,0,995.667,1,998,6,5,0.9,96,1.2,1.9,100,0,5.16657e-10,0.00422392,1.09592e-19,7.20028e-16,0,5,0,0
0,7.444,2013-Jul-11 17:12:19.732209,5048,4,0,0,995.75,1,998,4,6,0.8,96,1.1,2.1,100,0,5.11491e-10,0.00418168,1.08497e-19,7.12828e-16,0,6,0,0
0,7.446,2013-Jul-11 17:12:19.733612,5049,3,0,0,994,1,995,3,4,0.8,96.1,1,2.1,100,0,5.06376e-10,0.00413986,1.07412e-19,7.05699e-16,0,4,0,0
0,7.447,2013-Jul-11 17:12:19.734998,5050,6,0,0,994.833,1,997,6,3,0.7,96.1,0.8,2.4,100,0,5.01312e-10,0.00409846,1.06337e-19,6.98642e-16,0,3,0,0
0,7.448,2013-Jul-11 17:12:19.736485,5051,3,0,0,992.667,1,995,3,6,0.8,96.1,0.7,2.4,100,0,4.96299e-10,0.00405748,1.05274e-19,6.91656e-16,0,6,0,0
0,7.45,2013-Jul-11 17:12:19.737768,5052,0,0,0,992.667,1,995,0,3,0.8,96.1,0.6,2.5,100,0,4.91336e-10,0.0040169,1.04221e-19,6.84739e-16,0,3,0,0
0,7.451,2013-Jul-11 17:12:19.739144,5053,3,0,0,994.667,1,996,3,0,0.7,96.2,0.8,2.3,100,0,4.86423e-10,0.00397673,1.03179e-19,6.77892e-16,0,0,0,0
0,7.453,2013-Jul-11 17:12:19.740565,5054,3,0,0,995.333,1,998,3,3,0.7,96.1,0.9,2.3,100,0,4.81558e-10,0.00393697,1.02147e-19,6.71113e-16,0,3,0,0

==> /tmp/onemax_test_result_monitor_1 <==
1,7.439,2013-Jul-11 17:12:19.728267,5045,390,0,0,995.259,1,999,390,387,0.7,96.5,1,1.8,100,0,0.00234127,0.00498759,1.6014e-08,3.10971e-13,1,377,3,6
1,7.44,2013-Jul-11 17:12:19.729658,5046,380,0,0,995.237,1,999,380,390,0.9,96.3,1,1.8,100,0,0.00231785,0.00501729,1.58539e-08,3.07861e-13,5,370,9,6
1,7.442,2013-Jul-11 17:12:19.731068,5047,386,0,0,995.249,1,999,386,380,1,96.3,1.1,1.6,100,0,0.00229467,0.0050482,1.56953e-08,3.04782e-13,6,366,5,3
1,7.443,2013-Jul-11 17:12:19.732469,5048,385,0,0,995.257,1,999,385,386,0.8,96.5,0.9,1.8,100,0,0.00227173,0.00505236,1.55384e-08,3.01735e-13,4,371,5,6
1,7.445,2013-Jul-11 17:12:19.733875,5049,389,0,0,995.244,1,999,389,385,0.6,96.6,0.9,1.9,100,0,0.00224901,0.00502879,1.5383e-08,2.98717e-13,3,374,2,6
1,7.446,2013-Jul-11 17:12:19.735263,5050,384,0,0,995.26,1,999,384,389,0.7,96.7,0.7,1.9,100,0,0.00222652,0.00505872,1.52292e-08,2.9573e-13,5,374,2,8
1,7.447,2013-Jul-11 17:12:19.736676,5051,382,0,0,995.236,1,999,382,384,0.7,96.5,0.9,1.9,100,0,0.00220425,0.00508834,1.50769e-08,2.92773e-13,3,367,5,9
1,7.449,2013-Jul-11 17:12:19.738014,5052,390,0,0,995.287,1,999,390,382,0.5,96.4,1.2,1.9,100,0,0.00218221,0.0051192,1.49261e-08,2.89845e-13,0,372,2,8
1,7.45,2013-Jul-11 17:12:19.739404,5053,389,0,0,995.275,1,999,389,390,0.5,96.3,1.2,2,100,0,0.00216039,0.00512178,1.47769e-08,2.86947e-13,2,380,2,6
1,7.451,2013-Jul-11 17:12:19.740817,5054,384,0,0,995.276,1,1000,384,389,0.5,96.3,1.2,2,100,0,0.00213879,0.00514951,1.46291e-08,2.84077e-13,3,373,5,8

==> /tmp/onemax_test_result_monitor_2 <==
2,7.437,2013-Jul-11 17:12:19.728020,5045,3,0,0,995.667,1,996,3,7,0.9,96.3,1,1.8,100,0,1.50296e-05,0.00861104,3.46387e-16,1.62902e-18,0,7,0,0
2,7.439,2013-Jul-11 17:12:19.729416,5046,9,0,0,995.333,1,998,9,3,0.8,96.1,1,2.1,100,0,1.48793e-05,0.00852493,3.42923e-16,1.61273e-18,0,3,0,0
2,7.44,2013-Jul-11 17:12:19.730821,5047,5,0,0,994.4,1,997,5,9,0.7,96.4,0.9,2,100,0,1.47305e-05,0.00843968,3.39494e-16,1.59661e-18,0,9,0,0
2,7.442,2013-Jul-11 17:12:19.732213,5048,5,0,0,994.4,1,998,5,5,0.6,96.2,1,2.2,100,0,1.45832e-05,0.00835528,3.36099e-16,1.58064e-18,0,5,0,0
2,7.443,2013-Jul-11 17:12:19.733615,5049,2,0,0,995,1,995,2,5,0.7,96.2,0.8,2.3,100,0,1.44374e-05,0.00827173,3.32738e-16,1.56483e-18,0,5,0,0
2,7.444,2013-Jul-11 17:12:19.734990,5050,2,0,0,996,1,997,2,2,1.1,96.1,0.7,2.1,100,0,1.4293e-05,0.00818901,3.2941e-16,1.54919e-18,0,2,0,0
2,7.446,2013-Jul-11 17:12:19.736401,5051,6,0,0,996,1,999,6,2,1.1,96.1,0.7,2.1,100,0,1.41501e-05,0.00810712,3.26116e-16,1.53369e-18,0,2,0,0
2,7.447,2013-Jul-11 17:12:19.737772,5052,2,0,0,995,1,996,2,6,1,96.2,0.7,2.1,100,0,1.40086e-05,0.00802605,3.22855e-16,1.51836e-18,0,6,0,0
2,7.448,2013-Jul-11 17:12:19.739145,5053,2,0,0,995.5,1,997,2,2,1,96.4,0.6,2,100,0,1.38685e-05,0.00794579,3.19626e-16,1.50317e-18,1,1,0,0
2,7.45,2013-Jul-11 17:12:19.740564,5054,5,0,0,995.8,1,998,5,2,0.8,96.4,0.9,1.9,100,0,1.37298e-05,0.00786633,3.1643e-16,1.48814e-18,0,2,0,0

==> /tmp/onemax_test_result_monitor_3 <==
3,7.436,2013-Jul-11 17:12:19.728020,5045,6,0,0,992.667,1,998,6,5,1,95.9,1.2,1.9,100,0,1.15056e-11,0.00290087,3.13166e-17,1.97383e-17,0,5,0,0
3,7.437,2013-Jul-11 17:12:19.729411,5046,6,0,0,995.5,1,998,6,6,1,96,1.1,1.9,100,0,1.13905e-11,0.00287186,3.10035e-17,1.95409e-17,0,6,0,0
3,7.439,2013-Jul-11 17:12:19.730816,5047,3,0,0,995.667,1,997,3,6,0.8,96,1.5,1.7,100,0,1.12766e-11,0.00284314,3.06934e-17,1.93455e-17,0,6,0,0
3,7.44,2013-Jul-11 17:12:19.732210,5048,6,0,0,995.333,1,998,6,3,0.8,96.2,1.5,1.5,100,0,1.11638e-11,0.00281471,3.03865e-17,1.9152e-17,0,3,0,0
3,7.442,2013-Jul-11 17:12:19.733621,5049,6,0,0,996.667,1,998,6,6,1.2,96.2,1.2,1.4,100,0,1.10522e-11,0.00278657,3.00826e-17,1.89605e-17,0,6,0,0
3,7.443,2013-Jul-11 17:12:19.735004,5050,8,0,0,995.5,1,998,8,6,1.2,96.3,1.2,1.3,100,0,1.09417e-11,0.0027587,2.97818e-17,1.87709e-17,1,5,0,0
3,7.444,2013-Jul-11 17:12:19.736492,5051,9,0,0,997.111,1,999,9,8,1.1,96.3,0.9,1.7,100,0,1.08323e-11,0.00273111,2.9484e-17,1.85832e-17,0,7,1,0
3,7.446,2013-Jul-11 17:12:19.737780,5052,8,0,0,994.875,1,998,8,9,1.1,96.2,1,1.7,100,0,1.07239e-11,0.0027038,2.91891e-17,1.83974e-17,0,9,0,0
3,7.447,2013-Jul-11 17:12:19.739152,5053,6,0,0,996,1,998,6,8,1,96.2,1.3,1.5,100,0,1.06167e-11,0.00267676,2.88972e-17,1.82134e-17,0,8,0,0
3,7.448,2013-Jul-11 17:12:19.740573,5054,8,0,0,995.625,1,998,8,6,0.9,96.6,1.1,1.4,100,0,1.05105e-11,0.00265,2.86083e-17,1.80313e-17,0,6,0,0

Data mining


In [10]:
data_set = [pd.read_csv('/tmp/onemax_test_result_monitor_%d' % i, index_col=['DateTime','migration'], parse_dates='DateTime') for i in range(N)]
mig_set = [data_set[i].reset_index(0) for i in range(N)]

Attractivité des opérateurs

Nous illustrons ci-dessous l'actractivité sans et avec le cumul des valeurs.


In [11]:
attractiveness = pd.concat([pd.concat([mig_set[j]['P%dto%d' % (j,i)] for j in range(N)],axis=1).sum(axis=1) for i in range(N)],axis=1)
attractiveness.rename(columns=dict(zip(attractiveness.columns,OPS)), inplace=True)
fig, axes = subplots(nrows=2,ncols=2)
for affinity, ax in [(1,axes[0,0]), (10,axes[0,1]), (100,axes[1,0]), (1000,axes[1,1])]:
    attractiveness[::affinity].plot(ax=ax, title="smoothing = %d" % affinity).set_ylabel('nb individuals')
attractiveness.cumsum().plot(title='sum of cumul').set_ylabel('cumul of nb individuals')


Out[11]:
<matplotlib.text.Text at 0x7f6f565a6410>

Evolution des populations


In [12]:
nbindis = pd.concat([mig_set[i]['nb_individual_isl%d' % i] for i in range(N)], axis=1)
nbindis.rename(columns=dict(zip(nbindis.columns,OPS)), inplace=True)
nbindis_max = nbindis.max(axis=1); nbindis_max.name = 'nbindis max'
nbindis_avg = nbindis.mean(axis=1); nbindis_avg.name = 'nbindis avg'
#nbindis = nbindis.join(nbindis_max).join(nbindis_avg)
fig, axes = subplots(nrows=2,ncols=2)
for affinity, ax in [(1,axes[0,0]), (10,axes[0,1]), (100,axes[1,0]), (1000,axes[1,1])]:
    nbindis[::affinity].plot(ax=ax, title="smoothing = %d" % affinity).set_ylabel('nb individuals')
[ax.set_ylabel('nb individuals') for ax in nbindis[::A].plot(subplots=True, title="smoothing = %d" % A)]
nbindis.cumsum().plot(title='sum of cumul').set_ylabel('cumul of nb individuals')


Out[12]:
<matplotlib.text.Text at 0x7f6f56207fd0>

In [13]:
fig, ax = subplots()
ax.set_ylabel('nb individuals')
nbindis.boxplot(ax=ax)


Out[13]:
{'boxes': [<matplotlib.lines.Line2D at 0x7f6f5616c390>,
  <matplotlib.lines.Line2D at 0x7f6f55f8bb90>,
  <matplotlib.lines.Line2D at 0x7f6f56149c90>,
  <matplotlib.lines.Line2D at 0x7f6f55ffb990>],
 'caps': [<matplotlib.lines.Line2D at 0x7f6f5616c110>,
  <matplotlib.lines.Line2D at 0x7f6f5616cf90>,
  <matplotlib.lines.Line2D at 0x7f6f56141490>,
  <matplotlib.lines.Line2D at 0x7f6f55f8bf50>,
  <matplotlib.lines.Line2D at 0x7f6f56165910>,
  <matplotlib.lines.Line2D at 0x7f6f561492d0>,
  <matplotlib.lines.Line2D at 0x7f6f560e4d90>,
  <matplotlib.lines.Line2D at 0x7f6f560e4c90>],
 'fliers': [<matplotlib.lines.Line2D at 0x7f6f56171890>,
  <matplotlib.lines.Line2D at 0x7f6f56117b50>,
  <matplotlib.lines.Line2D at 0x7f6f55f8eb90>,
  <matplotlib.lines.Line2D at 0x7f6f560f4d50>,
  <matplotlib.lines.Line2D at 0x7f6f56207750>,
  <matplotlib.lines.Line2D at 0x7f6f56207610>,
  <matplotlib.lines.Line2D at 0x7f6f5613ca90>,
  <matplotlib.lines.Line2D at 0x7f6f5613c790>],
 'medians': [<matplotlib.lines.Line2D at 0x7f6f56171a50>,
  <matplotlib.lines.Line2D at 0x7f6f55f8e1d0>,
  <matplotlib.lines.Line2D at 0x7f6f56149b50>,
  <matplotlib.lines.Line2D at 0x7f6f55ffb650>],
 'whiskers': [<matplotlib.lines.Line2D at 0x7f6f55fa2950>,
  <matplotlib.lines.Line2D at 0x7f6f55fa2d50>,
  <matplotlib.lines.Line2D at 0x7f6f56117210>,
  <matplotlib.lines.Line2D at 0x7f6f56141d10>,
  <matplotlib.lines.Line2D at 0x7f6f560f4490>,
  <matplotlib.lines.Line2D at 0x7f6f56165c10>,
  <matplotlib.lines.Line2D at 0x7f6f5620f310>,
  <matplotlib.lines.Line2D at 0x7f6f5620f350>]}

In [14]:
nbindis.describe()


Out[14]:
bit-flip 1-flip 3-flip 5-flip
count 5055.000000 5055.000000 5055.000000 5055.000000
mean 9.942631 314.306825 13.079723 62.670821
std 24.748915 142.494820 37.662028 122.323845
min 0.000000 0.000000 0.000000 0.000000
25% 3.000000 376.000000 2.000000 7.000000
50% 4.000000 382.000000 4.000000 9.000000
75% 7.000000 386.000000 5.000000 14.000000
max 287.000000 396.000000 216.000000 394.000000

Évolution des solutions


In [15]:
bests = pd.concat([mig_set[i]['best_value_isl%d' % i] for i in range(N)], axis=1)
bests.rename(columns=dict(zip(bests.columns,OPS)), inplace=True)
bests_max = bests.max(axis=1); bests_max.name = 'bests max'
bests_avg = bests.mean(axis=1); bests_avg.name = 'bests avg'
#bests = bests.join(bests_max).join(bests_avg)
bests[::A].plot().set_ylabel('fitness')


Out[15]:
<matplotlib.text.Text at 0x7f6f560fac50>

Évolution de la fitness


In [16]:
nbindis_bests_max = nbindis.join(bests_max).set_index('bests max')
fig, axes = subplots(nrows=2,ncols=2)
for affinity, ax in [(1,axes[0,0]), (10,axes[0,1]), (100,axes[1,0]), (1000,axes[1,1])]:
    ax = nbindis_bests_max[::affinity].plot(ax=ax, title='smoothing = %d' % affinity)
    ax.set_ylabel('nb individuals')
    ax.set_xlabel('fitness')



In [ ]: