$1)$ On Probabilistic Search Algorithms: Implementing and Experimenting with Randomized Hill Climbing with Resampling Raunak

Third Draft

Implement a randomized hill climbing algorithm with resampling, called RHCR$2$ in the following, and conduct a set of experiments, minimizing the following function f:

fFrog$($x$,$y$)=$ x$$cos$($sqrt$(|$x$+$y$+1|))$sin$($sqrt$(|$y$$x$+1|))+$

$(1+$y$)$sin$($sqrt$(|$x$+$y$+1|))$cos$($sqrt$(|$y$$x$+1|))$

with x$,$y$[512,512]$

Your procedure should be called RHCR$2$ and have the following input parameters:

$$ sp: is the starting point of the Randomized Hill Climbing Resampling$2($RHCR$2)$ run

$$ p: the number of neighbors of the current solution that will be generated

$$ z: neighborhood size: for example, if z is set to z$=10,$ p neighbors for the current solution s are generated by adding vectors v $=($z$1,$ z$2)$ with z$1$ and z$2$ being random numbers in $[-10,+10]$ uniformly distributed

$$ seed: which is an integer that will be used as the seed for the random generator you employ in your implementation.

Figure $2$: Visualization of fFrog

RHCR$2$ runs Randomized Hill Climbing $3$ times, using sp as the starting position for the first run, the result of the first run sol$1$ as the start position of the second run which uses a smaller neighborhood size of z$/20,$ and uses the result of the second run sol$2$ as the starting position of the third run which uses a much smaller neighborhood size of z$/400,$ returning sol$3.$ RHCR$2$ returns sol$1,$ sol$2,$ and sol$3$ as well as f$($sol$1),$f$($sol$2)$ and f$($sol$3)$ and reports how often function f was called in the three runs of RHC and the total number of calls.

RHCR$2($sp$,$z$,$p$,$seed$)$;

sol$1=$RHC$($sp$,$z$,$p$,$seed$)$;

sol$2=$RHC$($sp$,$z$/20,$p$,$sol$1,$seed$)$;

sol$3=$RHC$($sp$,$z$/400,$p$,$sol$2,$seed$)$;

Return $\{($sol$1,$f$($sol$1)),($sol$2,$f$($sol$2)),($sol$3,$f$($sol$3))\}$;

Algorithm$1$: Pseudo code of RHCR@

$$

Run your randomized hill climbing procedure RHCR$2$ twice for the following parameters:

sp $=(-300,-400),(0,0),(-222,-222),(-510,400)$

p $=120$ and $400$; z $=9$ and $50$

REPORT

$1.$ For each of the $32$ runs report:

a$.$ the best solution $($x$,$ y$)$ found and its value for f

b$.$ number of solutions generated during the run $.$

$2.$ Summarize your results in $4$ tables using the format depicted in Fig. $2$; one for each p and z combination $($see example below$).$

$3.$ Finally, run RHCR$2$ one more time with $$your preferred choice$$ of values for sp$,$ p$,$ z$,$ and report the result; students, who find better solutions in this $33$rd run will get more points for the $33$rd run subtask.

$4.$ Interpret the obtained results evaluating solution quality, algorithm speed, impact of sp$,$ p$,$ and z on solution quality and algorithm speed. Summarize and interpret the complexity of the RHCR$2$ runs!

$5.$ Did the resampling option lead to better solutions? Do you believe with other values for p and z better results could be accomplished? Finally, assess if RHCR$2$ did a good, medium, or bad job in computing a $($local$)$ minimum for f$.$

p$/$z for sp $=(-300,-400),$

p$=120$ & z$=9$ Run$1$

Run$2$

Number of solutions searched in the first, second and third run of RHC$,$ and the sum of the $3$ numbers

in

S s

Result f$($sol$1),$f$($sol$2),$f$($sol$3)...$ Bes $...$ F $...$

p$=120$ & z$=50$

p$=400$ & z$=9$

p$=400$ & z$=50$

Fig. $3$: Table Template to report the results of the $33$ runs of RHCR$2$

You should summarize your results in $4/8$ tables formatted as the above, for each of the $4$ combinations of p & z$.$ Don$$t forget to summarize the results of your $33$rd run and to provide the other information asked for in the task specification!