Question $2$: Solve the above problem $(1)-(2)$ using the local search algorithm FM$.$ Use

your initial solution $x^0=(x_1,x_2,$cdots,$x_{16})$ where $x_i=0$ if the index $i$ in $x_i$ is even and

$x_i=1$ if the index $i$ is odd. The step by step description of the Fiduccia and Mattheyses

algorithm is given below:

The Fiduccia and Mattheyses $($FM$)$ Algorithm

Take the initial $x^0,$ calculate $f(x^0),$ set $x^{\text{m}\text{a}\text{x}}=x^0$; flag $=1,$ Pass $=1$

Let $F$ be the set of indices corresponding to unlocked$/$free variables $($initially $F=$

$\{1,2,$cdots,$n\}.$ Let $L$ be the set of indices corresponding to locked variables $($initially

$L=\frac{O}{?})$

WHILE flag $=1$

$3\mathrm{.}1$ Set flag $=0$ & Epoch $=0.$ Set $F=\{1,2,$cdots,$n\},L=\frac{O}{?}$

$3\mathrm{.}1\mathrm{.}1$ Until Epoch $=n$ DO

$3\mathrm{.}1\mathrm{.}2$ For each jinF based on for Epoch$=0),$ calculate $x^j=(x_1,$cdots,$1\}$

$\{$:$x_j,$cdots,$x_n)$ by flipping $x_j$ and find $f(x^j).$

$3\mathrm{.}1\mathrm{.}3$ Let $x^t=argma{x}_j\{f(x^j),$jinF$\}.$ Set $,$ Epoch$=$Epoch$+1$

$3\mathrm{.}1\mathrm{.}4$ EndDO

$3\mathrm{.}2$ Let $x^t$ be the best solution at the end of the $t-$th Epoch and $x=argma{x}_t\{\begin{array}{c}f(x^t)\\ \text{t}\text{i}\text{n}\end{array}$

L$\}$

$3\mathrm{.}3$ IF $f(x)>f(x^0)$

$3\mathrm{.}3\mathrm{.}1,x^{\text{m}\text{a}\text{x}}=x,x^0=x,$ flag $=1,$ Pass $=$ Pass $+1$

$3\mathrm{.}4$ ENDIF

ENDWHILE

RETURN $x^{\text{m}\text{a}\text{x}}$