TITLE: characteristic of ring
QUESTION [3 upvotes]: I’m a bit lost on the characteristic of a ring. It’s said the additive order of every non-zero element is the same.
But, consider ring $\mathbb{Z}_2\times \mathbb{Z}_{3}$, element $(0,1)$ has order $3$, but $(1,0)$ has order $2$, they are different.
Where is my misunderstanding?
— update:
I’m sorry, I missed the line in the original notes that the ring shall be entire.

REPLY [8 votes]: Fields work that way, more generally domains. The additive order of every nonzero element of a domain $R$ is the same.
Proof: Let $n$ be additive order of $1_R$, i.e. the smallest positive integer such that $n \cdot 1_R = 0_R$ (note that every ring is a $\mathbb Z$-algebra so we can multiply with integers). Then every element $x\in R$ with $x \neq 0_R$ satisfies $n \cdot x = n \cdot 1_R \cdot x = 0_R \cdot x = 0_R$, so the additive order $k$ of $x$ divides $n$. But if $k < n$, then $0_R = k \cdot x = (k \cdot 1_R) \cdot x$, so $x$ is a right zero divisor. But domains do not have zero divisors, so $k = n$.
The previous argument assumed that $1_R$ has finite order. But if the order of $1_R$ is infinite, then a similar argument shows that the order of all nonzero $x$ must be infinite.
But if $R$ is not a domain, this is not true in general. You've found an example yourself.


TITLE: Let k be a natural number. What is the probability of it being equal to a random number in group?
QUESTION [0 upvotes]: We have 6 groups:
A takes values from [0, 1, 2, 3, 4, 5, 6]
B takes values from [0, 1, 2, 3, 4, 5]
C takes values from [0, 1, 2, 3, 4]
D takes values from [0, 1, 2, 3]
E takes values from [0, 1, 2]
F takes values from [0, 1]
Each variable takes one of those values randomly, and independently from each other. What is the probability that k, is equal to A, the probability that k is equal to B, and so on for each of them. Given that $1\leq k \leq 6$.
For the first group I noticed the probability of it being each value is $1/7$.
For the second one, $1/6$.
.
.
.
For the last one $1/2$.
Unfortunately I am stuck since I don't know how to compare them to k.
As you can see, K can take any value from $1,...,n$. Where $n$ is the number of sets.

REPLY [0 votes]: For the first group, there are $6$ choices for $k$ and $7$ for $A$. So the total number of cases is $42$. The number of successful cases is $6, $ for $\{k=1,X[A]=6\}\cdots$ Therefore the probability is $\frac{6}{42}=\frac 17$ for the first group. Following the same logic, group $2$ has chance $\frac{5}{36}$, and group $3$ has chance $\frac{4}{30}=\frac{2}{15}$
The probability of $k$ equaling each set is therefore the product of all the chances.


TITLE: Evaluating $\lim_{x\to0^+}\frac{2x(\sin x)^2+\frac{2x^7+x^8}{3x^2+x^4}-\arctan(2x^3)}{\ln(\frac{1+x^2}{1-x^2})-2x^2+xe^{-{1\over x}}}$
QUESTION [2 upvotes]: To start with, the term $xe^{-{1\over x}}$ can be ignored.Then splitting the term $\ln(\frac{1+x^2}{1-x^2})=\ln(1+x^2)-\ln(1-x^2)$ and expanding both of them up to order 3 we have in the denominator $2x^2+{2x^6\over 3}-2x^2={2x^6\over3}$
As for the numerator $\arctan(2x^3)\sim2x^3$ and ${2x^7+x^8\over 3x^2+x^4}\sim{2\over3}x^5$.So if we expand $\sin x$ up to order 2,then take the square (ignoring higher order terms) and multiply by $2x$ we have $2x(\sin x)^2\sim2x^3-{2\over3}x^5$ which cancels out with the other terms,giving us an indeterminate form.So I think we should have $x^6$ term in the numerator.
But if I expand $\sin x$ up to order 3 and take square, I fail to obtain $x^5$ term(so that when multiplied by $2x$ gives me $x^6$).How can this be done?

REPLY [1 votes]: The Taylor series approach suggested by @Matteo and @WillJagy is the way to go.  Here is that approach made a bit more explicit:

Divide the numerator and denominator by x^6.
Construct the resulting first order Taylor series for both numerator and denominator.
Observe what the limits must be.

$$\lim_{x\to 0^+} \, \frac{-\tan ^{-1}\left(2 x^3\right)+\frac{(x+2) x^5}{x^2+3}+2 x \sin ^2(x)}{x \exp \left(-\frac{1}{x}\right)-2 x^2+\log \left(\frac{x^2+1}{1-x^2}\right)}$$
$$\lim_{x\to 0^+} \,{ {(\frac{1}{3}-\frac{2 x}{15}+o(x^2) )}\over{(\frac{2}{3}+e^{-1/x}(\frac{1}{x^5}+o(x^2)))}}=\frac{1}{2}$$
Here is a plot of the function:


text:
In this section we are going to present the results obtained by applying the proposed
algorithm, firstly to some test functions that are usually used as benchmarks
for optimization problems. Since this method is particularly suited for
high-dimensional functions, we analyze the optimization convergence for three
different input dimension ($2$, $15$, and $40$), i.e. the number of genes of
each individual.
The second test case we propose is instead a typical engineering problem,
where we optimize the lift-to-drag coefficient of a NACA airfoil which is
deformed using a map $\mathcal{M}: \mathbb{R}^{10} \to \mathbb{R}$ defined in
\cref{sec:naca}. \RA{In this example we opted for the use of a
  surrogate model only to evaluate the individuals' fitness for
computational considerations, since we just want to compare ASGA with
GA. We do not rely on the surrogate for the gradients
approximation. In~\cite{demo2021hull}, instead, we apply
ASGA on a naval engineering hydrodynamics problem, where we do not
rely on a surrogate model of the target function, but instead we
exploit data-driven model order reduction methods to reconstruct the
fields of interest and then compute the function to optimize.}

In both the test cases, in order
to collect a fair comparison, we adopt the same routines for the selection,
the mutation and the crossover steps.
In particular:
\begin{itemize}
\item for the {\it mate} we use the blend BLX-alpha
crossover~\cite{eshelman1993real} with $\alpha= 1.0$, with a mate probability
of $50\%$. With this method, the offspring results:
\begin{equation}
\label{eq:mating_general}
\begin{cases}
\RB{\mathbf{x}_a^i} = (1 - \gamma)\RB{\mathbf{x}_a^{i-1}} + \gamma \RB{\mathbf{x}_b^{i-1}}\\
\RB{\mathbf{x}_b^i} = \gamma \RB{\mathbf{x}_a^{i-1}} + (1 - \gamma)\RB{\mathbf{x}_b^{i-1}}
\end{cases}\quad \text{for}\;\RB{a, b} = 1, \dotsc, N,
\end{equation}
where $\RB{\mathbf{x}_a^{i-1}}$ and $\RB{\mathbf{x}_b^{i-1}}$ refer
       to the parent individuals (\RB{at the $i-1$th generation}), $\RB{\mathbf{x}_a^i}$
       and $\RB{\mathbf{x}_b^i}$ are the mated individuals, \RB{$N$ is the cardinality of population}, and
$\gamma$ is a random variable chosen in the interval $[-\alpha,
1+\alpha)$. \RA{We mention that \cref{eq:mating_general} can recover the graphical
  description of mating in \cref{fig:crossover} if $\gamma$ is taken to
  be discrete, either $0$ or $1$, and applied component-wise.}

\item for the {\it mutation}, a Gaussian
operator~\cite{hinterding1995gaussian} has been used with a mutation
probability of $50\%$. This strategy changes genes by adding a normal noise.
\RA{Since we do not have any knowledge about the low-dimensional space, tuning
the variance of such mutation may result in a not trivial procedure.  This
quantity has in fact to be set in order to explore the input space but,
as the same time, producing minimal differences between parents and
offspring. A fixed variance for both the spaces may cause a too big distance
--- in $l_2$ sense --- between parents and offspring, inhibiting the
convergence.}
To overcome this potential problem, we correlate the
Gaussian variance with the genes theirselves, ensuring a reasonable mutation in
both spaces. The adopted mutation method is:
\begin{equation}
	\RB{\mathbf{x}_a^i} = \RB{\mathbf{x}_a^{i-1}} + \varepsilon \, \RB{\mathbf{x}}_a^{i-1} \qquad \text{for}\;\RB{a} = 1, \dots, N,
\end{equation}
where $\varepsilon$ is a random variable with probability distribution
$\mathcal{N}(\mu, \sigma^2)$, that is $\varepsilon \sim \mathcal{N}(\mu,
\sigma^2)$, with $\mu = 0$ and $\sigma^2 = 0.1$.
\end{itemize}
Regarding the {\it selection}, since the limited number of individuals per
population, we adopt one of the simplest criteria, by selecting the $N$ best
individuals in terms of fitness.

We also keep fixed the additional
parameters for the AS extension: the number of active dimensions $M$ is set to
$1$, while the number of back-mapped points is $2$. \RB{All the gradients
computations are done using local linear models}. For the actual
computation regarding AS we used the ATHENA\footnote{Freely available
  at \url{https://github.com/mathLab/ATHENA}.} Python
package~\cite{romor2020athena}. The only varying parameters
are the size of the initial population $N_0$, the size of population during the
evolution $N$, and the number of generations in the evolutive loop, which are
chosen empirically based on the objective function. We \RA{emphasize} that, due to
the stochastic nature of these methods, we repeated the tests $15$ times, with
different initial configurations, presenting the mean value, the minimum and
the maximum over the $15$ runs.

\subsection{Benchmark test functions}
We applied the optimization algorithm to $6$ different $n$-dimensional test
functions, which have been chosen to cover a large variety of possible shapes.
For all the functions, the results of the proposed method are compared to the
results obtained using the standard genetic approach.  In detail, the
functions we tested are the so called: {\it Rosenbrock}, {\it Ackley}, {\it
Bohachevsky}, {\it Rastrigin}, {\it Schaffer N.\ 7} and {\it Zakharov}. In
Figure~\ref{fig:funcs} we depict the test functions, in their
two-dimensional form. In the
following paragraphs we briefly introduce them before presenting the
obtained results. For a complete literature survey on benchmark functions
for global optimization problems we suggest~\cite{jamil2013survey}.

\begin{figure}
    \centering
    \begin{subfigure}[b]{0.32\textwidth}
	    \includegraphics[width=\textwidth]{figures/rosenbrock.pdf}
        \caption{Rosenbrock function.}
        \label{fig:rosenbrock}
    \end{subfigure}
    \begin{subfigure}[b]{0.32\textwidth}
	    \includegraphics[width=\textwidth]{figures/ackley.pdf}
        \caption{Ackley function.}
        \label{fig:ackley}
    \end{subfigure}
    \begin{subfigure}[b]{0.32\textwidth}
	\includegraphics[width=\textwidth]{figures/bohachevsky.pdf}
        \caption{Bohachevsky function.}
        \label{fig:bohachevsky}
    \end{subfigure}

    \begin{subfigure}[b]{0.32\textwidth}
	\includegraphics[width=\textwidth]{figures/rastrigin.pdf}
        \caption{Rastrigin function.}
        \label{fig:rastrigin}
    \end{subfigure}
    \begin{subfigure}[b]{0.32\textwidth}
	    \includegraphics[width=\textwidth]{figures/schaffer.pdf}
        \caption{Schaffer N.\ 7 function.}
        \label{fig:schaffer}
    \end{subfigure}
    \begin{subfigure}[b]{0.32\textwidth}
	    \includegraphics[width=\textwidth]{figures/zacharov.pdf}
        \caption{Zakharov function.}
        \label{fig:zakharov}
    \end{subfigure}
    \caption{Benchmark test functions representation in 2D. White dots indicate the global minima.}\label{fig:funcs}
\end{figure}

\paragraph{(a) Rosenbrock function}
The Rosenbrock function is a widespread test function in the context
of global
optimization~\cite{dixon1978global,bect2012sequential,picheny2013benchmark}.
We choose it as representative of the valley-shaped test functions. The
general $d$-dimensional formulation is the following:
\begin{equation}
\label{eq:rosenbrock}
f(x) = \sum_{i=1}^{d-1} [100 (x_{i+1} - x_i^2)^2 + (x_i - 1)^2].
\end{equation}
Its global minimum is $f(x^*) = 0$, at $x^* = (1, 1, \dots, 1)$.
As we can see from \cref{fig:rosenbrock} the minimum lies on a
easy to find parabolic valley, but the convergence to the actual
minimum is notoriously difficult. We evaluated the function in the
hypercube $[-5, 10]^d$.

\paragraph{(b) Ackley function}
The Ackley function is characterized by many local minima making it
difficult to find the global minimum, especially for hillclimbing
algorithms~\cite{back1996evolutionary,adorio2005mvf}. The
general $d$-dimensional formulation is the following:
\begin{equation}
\label{eq:ackley}
f(x) = -a \exp \left( -b  \sqrt{\frac{1}{d}\sum_{i=1}^d x_i^2} \right)
- \exp \left( \sqrt{\frac{1}{d}\sum_{i=1}^d \cos(c x_i)} \right) + a + \exp(1),
\end{equation}
where $a$, $b$, and $c$ are set to $20$, $0.2$, and $2\pi$, respectively.
Its global minimum is $f(x^*) = 0$, at $x^* = (0, 0, \dots, 0)$.
As we can see from \cref{fig:ackley} the function is nearly
flat in the outer region, with many local minima, and the global
minimum lies on a hole around the origin. The function has been evaluated in
the domain $[-15, 30]^d$.

\paragraph{(c) Bohachevsky function}
The Bohachevsky function is a representative of the bowl-shaped
functions. There are many variants and we chose the
general $d$-dimensional formulation as the following:
\begin{equation}
\label{eq:bohachevsky}
f(x) = \sum_{i=1}^{d-1} (x_i^2 + 2x_{i+1}^2 - 0.3 \cos(3 \pi x_i) -
0.4 \cos(4 \pi x_{i+1}) + 0.7) .
\end{equation}
Its global minimum is $f(x^*) = 0$, at $x^* = (0, 0, \dots, 0)$.
As we can see from \cref{fig:bohachevsky} the function has a
clear bowl shape. This function has been evaluated in the domain $[-100, 100]^d$.

\paragraph{(d) Rastrigin function}
The Rastrigin function is another difficult function to deal with for
global optimization with genetic algorithm due to the large search
space and its many local
minima~\cite{muhlenbein1991parallel}. The general $d$-dimensional
formulation is the following:
\begin{equation}
\label{eq:rastrigin}
f(x) = 10 d + \sum_{i=1}^d [x_i^2 - 10 \cos(2 \pi x_i)].
\end{equation}
Its global minimum is $f(x^*) = 0$, at $x^* = (0, 0, \dots, 0)$.
As we can see from \cref{fig:rastrigin} the function is highly
multimodal with local minima regularly distributed. We evaluated this
function in the input domain $[-5.12, 5.12]^d$.

\paragraph{(e) Schaffer N.\ 7 function}
The Schaffer N.\ 7 function~\cite{schaffer1989study} is a stretched V
sine wave. The general $d$-dimensional
formulation is the following:
\begin{equation}
\label{eq:schaffer}
f(x) = \sum_{i=1}^{d-1} (x_i^2 + x_{i+1}^2)^{0.25} \left [ \sin^2 (50
  (x_i^2 + x_{i+1}^2)^{0.10} ) + 1 \right ] .
\end{equation}
Its global minimum is $f(x^*) = 0$, at $x^* = (0, 0, \dots, 0)$.
As we can see from \cref{fig:schaffer} the function presents
many local minima. The optimization has been performed in the hypercube $[-100,
100]^d$.

\paragraph{(f) Zakharov function}
The Zakharov function is a representative of the plate-shaped
functions. It has no local minima and one global minimum. The general
$d$-dimensional formulation is the following (after a shift):
\begin{equation}
\label{eq:zakharov}
	f(x) = \sum_{i=1}^d (x_i + 10)^2 + \left ( \sum_{i=1}^d \frac{i}{2} (x_i + 10)
	\right )^2 + \left ( \sum_{i=1}^d \frac{i}{2} (x_i+10) \right )^4.
\end{equation}
We \RA{emphasize} that we used a shifted version with global minimum
$f(x^*) = 0$, at $x^* = (-10, -10, \dots, -10)$. This choice is made
to prove that the proposed method is not biased towards minima around
the origin.
We can see from \cref{fig:zakharov} the function for $d=2$. We
evaluated the Zakharov function in the domain $[-15, 0]^d$.

\begin{figure}[htb]

\includegraphics[width=\textwidth]{figures/plot_2d.pdf}
\caption{Results of the optimization of the benchmark functions in a space of
	dimension $d = 2$. We compare the standard GA (in blue square dots) with
        the proposed algorithm ASGA (in red circle dots) using an initial population of size $30$, while
	the dimension for each generation is fixed to $10$. The solid lines
	represent the mean, over $15$ runs, of the objective function
        corresponding to the best individual at each generation. The shaded areas show
	the interval between minimum and maximum (blue with lines for
        GA, red for ASGA).\label{fig:opt2dim}}
\end{figure}

All the test cases presented share the same hyper-parameters described
at the beginning of this section, except for the population size. For
the $2$-dimensional benchmark functions, the two algorithms are tested
creating $N_0 = 200$ random individuals for the initial population,
then keeping an offspring of dimension $N = 100$. The \cref{fig:opt2dim}
shows the behaviour for all the test functions. For this space dimension, the
two trends are very similar: the usage of the proposed algorithm does not make
the optimization faster, and adds the computational overhead for the AS
construction. Despite that, the results after $10$ generations are
very similar, and we can consider this as a worst case scenario, where
a clear reduction in the parameter space is not possible.

\begin{figure}[htb]

\includegraphics[width=\textwidth]{figures/plot_15d.pdf}

\caption{Results of the optimization of the benchmark functions in a space of
	dimension $d = 15$. We compare the standard GA (in blue square dots) with
        the proposed algorithm ASGA (in red circle dots) using an initial population of size $2000$, while
	the dimension for each generation is fixed to $200$. The solid lines
	represent the mean, over $15$ runs, of the objective function
        corresponding to the best individual at each generation. The shaded areas show
	the interval between minimum and maximum (blue with lines for
        GA, red for ASGA).\label{fig:opt15dim}}
\end{figure}

The ASGA performance gain changes drastically increasing the number of
dimension to $d = 15$, as demonstrated in \cref{fig:opt15dim}. For such
dimension, the two parameters $N_0$ and $N$ are set to $2000$ and $200$,
respectively.  Starting from this dimension, it is \RA{possible} to note a
remarkable difference between the standard method and the proposed one. The
greater the input dimension, the greater the gain produced by ASGA,
due to the exploitation of the AS reduction. All the benchmarks show a
faster decay, but we can isolate two different patterns in the evolution:
\textit{Rosenbrock} and \textit{Ackley} show a very steep trend in the first
generation gain, while for the next generations the population is not able to
decrease its fitness as much as before, showing a quasi-constant behaviour. The
difference with the standard genetic algorithm is maximized in the first
generation, but even if the evolution using ASGA is not so effective after the
first generation in these two cases, the proposed method is able to achieve
anyway a better result (on average) after $30$ generations. The other
benchmarks instead show a much smoother decay, gradually converging to the optimum.
Despite the lack of the initial step, for these benchmarks the gain with
respect to the standard approach becomes bigger, even if after several
generations the convergence rate decreases.
\begin{figure}[htb]

\includegraphics[width=\textwidth]{figures/plot_eigs_as.pdf}
	\caption{Eigenvalues estimates of the matrix $\mathbf{C}$ in
          \cref{eq:cov_matrix} for all the benchmarks, at
          the first generation, for $d = 15$. The black dots in the plot indicate
          the eigenvalues, while the grey area is defined by the
          bootstrap intervals.\label{fig:as_eigs}}
\end{figure}
In order to better understand these differences, we investigate the spectra of the AS
covariance matrices for all the benchmarks, which are reported in
\cref{fig:as_eigs}. The patterns individuated in the optimizations are
partially reflected in the eigenvalues: \textit{Rosenbrock}, \textit{Ackley}
and \textit{Zakharov} have an evident gap between the first and the second
eigenvalues, which results in a better approximation (of the original function) in
the $1$-dimensional subspace. However, the order of magnitude of the first
eigenvalue is different between the three functions: for \textit{Rosenbrock}
and \textit{Ackley} the magnitude is greater than~$\num{0.1}$ whereas for
\textit{Zakharov} is around~$\num{0.05}$.

\begin{figure}[p!]

\includegraphics[width=\textwidth]{figures/plot_15d_2.pdf}
\includegraphics[width=\textwidth]{figures/plot_15d_5.pdf}
\caption{\RA{Results of the optimization of the benchmark functions in a space of
	dimension $d = 15$, with active dimension $M=2$ (top) and $M=5$
	(bottom). We compare the standard GA (in blue square dots) with the
	proposed algorithm ASGA (in red circle dots) using an initial
	population of size $2000$, while the dimension for each generation is
	fixed to $200$. The solid lines represent the mean, over $15$ runs, of
	the objective function
        corresponding to the best individual at each generation. The shaded areas show
	the interval between minimum and maximum (blue with lines for
        GA, red for ASGA).}\label{fig:opt15dim_as}}
\end{figure}

\RA{Since for all the tests, the ASGA approach performs better than its
classical counterpart despite the absence, in some cases, of an
evident spectral gap in the AS covariance matrix, we perform further
investigations. In particular, we use the
same tests as before ($15$-dimensional functions) but with a different
number of active dimensions, i.e.\ $M =
\{2, 5\}$, instead of $M = 1$. In \cref{fig:opt15dim_as} we show the
comparison between the classical GA and the ASGA outcomes. It is
possible to note that by increasing the active
dimension, the differences between the performances of the two methods become
smaller. Only for the Rosenbrock and for the Ackley functions we can see that ASGA with $M = 5$
is not able to reach the same order of magnitude reached by GA (we remark the original
space has dimension $d=15$).}

\begin{figure}[htb]

\includegraphics[width=\textwidth]{figures/plot_40d.pdf}
\caption{Results of the optimization of the benchmark functions in a space of
	dimension $d = 40$. We compare the standard GA (in blue square dots) with
        the proposed algorithm ASGA (in red circle dots) using an initial population of size $5000$, while
	the dimension for each generation is fixed to $1000$. The solid lines
	represent the mean, over $15$ runs, of the objective function
        corresponding to the best individual at each generation. The shaded areas show
	the interval between minimum and maximum (blue with lines for
        GA, red for ASGA).\label{fig:opt40dim}}
\end{figure}

Increasing the input dimension to $d = 40$ \RA{shows a much clearer benefit} in using
the proposed method, as we can see in \cref{fig:opt40dim}. Here we set $N_0
= 5000$ and $N = 1000$. \RA{We specify that we set the active dimension $M=1$}.
Also with this dimensionality, we are able to isolate
two main behaviours in the convergence of the six benchmarks: a very steep
trend in the first generation, and a more smooth one, but still equally
effective. The interesting thing is that some benchmarks do not reflect the
behaviour collected with $d = 15$. While \textit{Rosenbrock},
\textit{Rastrigin} and \textit{Zakharov} show a similar convergence
rate for ASGA, the other benchmarks present a change in the slope. The
different behaviours observed for the same benchmarks
evaluated at different input dimensional spaces is due to the fact
that the method is sensitive to the approximation accuracy of the
gradients of the model function with respect to the input data. This
is an issue inherited by the application of AS. Moreover, since we are
keeping just one active variable, we are discarding several
information, thus the representation of the function along the active
subspace could present some noise. So the genetic procedure
enhanced by AS is able to converge fast to the optimum, but this
optimum may be --- for the space simplification --- distant to the true optimum.
\RA{From the tests with higher active dimension, we note that the improvement
in the first iterations is not as rapid as by using a $1$-dimensional AS. Also, keeping
more active dimensions, the performance of ASGA becomes similar to the
standard GA. We can conclude that with one (or few) active dimension,
ASGA reaches the global minimum with less function evaluations, but we
get stuck with the projection error introduced by AS, whereas by
increasing the active dimension we reduce the projection error but we
lose the effectiveness of the evolution steps in a reduced space.} A possible solution for
this problem can be a smarter (and dynamical) strategy to select the number of
active dimensions.

Over all the three test cases, where we vary the input space dimension, the
performance of ASGA are better or equal than the standard GA. In
\cref{tab:bench} we summarize the relative gain on average achieved after the entire evolution
and after only one generation, divided by test function, both with the GA and
ASGA methods. The relative gain is computed as the mean over $15$ runs
of the ratio between the objective function
evaluated at the best-fit individual at the beginning of the evolution
($f(x_{\text{opt}}^{0})$) and the
objective function evaluated at the best-fit individual after $k$
generations, with $k=1$ and $k=N_{\text{gen}}$, where $N_{\text{gen}}$
is the maximum number of generations depending on the input
dimension. This relative gain $G(k)$ reads,
\begin{equation}
  \label{eq:gain}
G(k) = \frac{1}{15}\sum_{i=1}^{15} f(x_{\text{opt}_i}^{0}) /  f(x_{\text{opt}_i}^k),
\end{equation}
where $x_{\text{opt}_i}^k$ is the best-fit individual of the population at the $i$-th
run and at $k$-th generation. Highest values correspond to a more effective
optimization, and for dimensions $15$ and $40$ we can see from
\cref{tab:bench} that ASGA performs better than standard GA for all
the benchmarks. Even the gain after just one
evolutive iteration is bigger in all the collected tests, reaching in some
cases some order of magnitude of difference with respect to GA.
These results suggest that despite the computational overhead for the
construction of AS and the back-mapping, an application of the ASGA
over the standard GA produces usually better or at least comparable results for
a fixed generation.

\begin{table}[htb]
\begin{center}
    \caption{Summary comparison between GA and ASGA with respect to
      the gain $G(k)$ defined in \cref{eq:gain}. We compare the
      gain for the first and for the last generation.\label{tab:bench}}
\footnotesize
\begin{tabular}{ ll|rr|rr|rr }
\hline
\hline
  \multirow{2}{*}{\bf Function}  & \multirow{2}{*}{\bf Method} &
      \multicolumn{2}{c}{\bf dim = 2}  &
      \multicolumn{2}{c}{\bf dim = 15} &
      \multicolumn{2}{c}{\bf dim = 40} \\
    && $G(9)$ & $G(1)$ &
      $G(29)$ & $G(1)$ &
      $G(49)$ & $G(1)$ \\
\hline
\rowcolor{Gray}
                         & GA   & 9.17 & 1.13 & 4.71 & 1.03 & 2.53  & 1.10\\
\rowcolor{Gray}
\multirow{-2}{*}{Ackley} & ASGA & 2.93 & 1.29 & 5.81 & 3.89 & 20.91 & 3.00\\

                              & GA   & 39.58 & 1.78 & 223.86  &   1.22 &   729.05 & 1.81   \\
\multirow{-2}{*}{Bohachevsky} & ASGA & 31.66 & 2.04 & 8608.41 & 130.72 & 75104.33 & 3548.70\\

\rowcolor{Gray}
                            & GA   & 7.34 & 1.41 &    3.80 & 1.05 &     6.97 &  1.17\\
\rowcolor{Gray}
\multirow{-2}{*}{Rastrigin} & ASGA & 3.24 & 1.39 & 1343.41 & 4.00 & 14738.40 & 71.77\\

                             &  GA  & 30.04 & 1.74 &  335.33 &   1.34 &  1723.89 &    2.42\\
\multirow{-2}{*}{Rosenbrock} & ASGA & 39.68 & 2.66 & 2343.57 & 167.48 & 29747.56 & 1600.24\\

\rowcolor{Gray}
                           &  GA  & 3.64 & 1.21 &  4.83 & 1.11 &  5.66 &  1.18\\
\rowcolor{Gray}
\multirow{-2}{*}{Schaffer} & ASGA & 2.16 & 1.17 & 16.41 & 3.61 & 32.57 & 10.38\\

                           &  GA  & 38.59 & 2.65 &   3.11 &  1.07 &  2148.39 & 26.50\\
\multirow{-2}{*}{Zakharov} & ASGA & 51.14 & 3.88 & 417.86 & 24.46 & 37739.61 & 237.48 \\
  \hline
  \hline
\end{tabular}
\end{center}
\end{table}

\subsection{Shape design optimization of a NACA airfoil}
\label{sec:naca}
Here we present the shape design optimization of a NACA 4412
airfoil~\cite{abbott2012theory}. Since the purpose of this work is limited to
the extension of the GA, we briefly present the details of the
complete model, with a quick overview of the application. To reproduce
the full order simulations please refer to~\cite{tezzele2019mortech}.

\RB{Let be given the unsteady incompressible Navier-Stokes equations
described in an Eulerian framework on a parametrized space-time domain
$Q(\mupar) = \Omega \times [0,T] \subset
\R^d\times\R^+$, $d=2,3$ with the
velocity field denoted by $\mathbf{u}: Q(\mupar) \to \R^d$, and the
pressure field by $p: Q(\mupar) \to \R$, such that:
\begin{equation}
\label{eq:navstokes}
\begin{cases}
\mathbf{u_t}+ \mathbf{\nabla} \cdot (\mathbf{u} \otimes \mathbf{u})- \mathbf{\nabla} \cdot
2 \nu \mathbf{\nabla^s} \mathbf{u}=-\mathbf{\nabla}p &\mbox{ in } Q(\mupar),\\
\mathbf{\nabla} \cdot \mathbf{u}=\mathbf{0} &\mbox{ in } Q(\mupar),\\
\mathbf{u} (t,x) = \mathbf{f}(\mathbf{x}) &\mbox{ on } \Gamma_{\text{in}} \times [0,T],\\
\mathbf{u} (t,x) = \mathbf{0} &\mbox{ on } \Gamma_{0}(\mupar) \times [0,T],\\
(\nu\nabla \mathbf{u} - p\mathbf{I})\mathbf{n} = \mathbf{0} &\mbox{ on } \Gamma_{\text{out}} \times [0,T],\\
\mathbf{u}(0,\mathbf{x})=\mathbf{k}(\mathbf{x}) &\mbox{ in } Q(\mupar)_0,\\
\end{cases}
\end{equation}
holds.  Here, we have that $\Gamma = \Gamma_{\text{in}} \cup \Gamma_{0} \cup \Gamma_{\text{out}}$
is the boundary of $\Omega$ and it is composed by the inlet boundary
$\Gamma_{\text{in}}$, the outlet boundary $\Gamma_{\text{out}}$ and the
physical walls $\Gamma_0(\mupar)$. The
term $\mathbf{f}(\mathbf{x})$ stands for the stationary non-homogeneous boundary
condition, whereas $\mathbf{k}(\mathbf{x})$ indicates the initial condition for
the velocity at $t=0$. Shape changes are applied to the boundary
$\Gamma_0(\mupar)$ corresponding to the airfoil
wall, which in the undeformed configuration corresponds to
the 4-digits, NACA~4412 wing profile. Such shape modifications are
associated to numerical parameters contained in the
vector $\mupar \in \R^k$ with $k=10$.}

As geometrical deformation map
$\mathcal{M}$ we adopt the shape morphing proposed
in~\cite{hicks1978wing}, where 5 shape functions $r_i$ are added to the
upper and lower part of the airfoil profile denoted by $y^+$ and
$y^-$, respectively. Each shape function is multiplied by a possible
different coefficient as in the following
\begin{equation}
  y^+ = \overline{y^+} + \sum_{i=1}^5 a_i r_i , \qquad
  y^- = \overline{y^-} - \sum_{i=1}^5 b_i r_i ,
\end{equation}
where the bar denotes the reference undeformed profile.
These $10$ coefficients ($a_i$ and $b_i$) represent the input
parameters $\mupar \in \mathbb{D} := [0, 0.03]^{10}$. In
\cref{fig:bumps} we depict the NACA 4412 together with the $5$ rescaled
 shape functions $r_i$.
The output function we want to maximize is the lift-to-drag coefficient, one of the
typical quantities of interest in aeronautical problems. To recast the
problem in a minimization setting, we just minimize the opposite of
the coefficient. To compute it, we
model a turbulent flow pasting around the 2D airfoil using the incompressible
Reynolds Averaged Navier--Stokes equations. Regarding the main numerical
settings, we adopt a finite volume approach with the Spalart--Allmaras model,
with a computational grid of $46500$ degrees of freedom. The flow velocity, at
the inlet boundary, is set to $1$ m/s, while the Reynolds number is fixed
to $50000$.
For the detailed problem formulation we refer to the experiments conducted
in~\cite{tezzele2019mortech}.

Instead of running the high-fidelity solver for any new untested parameter, we optimize a
\RB{RBF} response surface built using the initial dataset. Due to the stochastic nature of the method, also in
this test case we test the methods for several initial settings --- $25$
different runs --- making the total computational load very high. Thus, we
decided to build a response surface using a dataset of $333$ samples, computed
with the numerical scheme described above, mimicking at the same time a typical
industrial workflow.

The objective function $f_{\text obj} (\mupar ) : \mathbb{D} \subset
\R^{10} \to \R$ we are going to minimize is the following:
\begin{equation}
f_{\text obj}(\mupar) = \begin{cases}
g(\mupar)\quad\text{if }\, \mupar  \in \mathbb{D},\\
\alpha\quad\quad\,\,\text{if }\, \mupar \notin \mathbb{D},\\
\end{cases}
\end{equation}
where $g(\mupar)$ is the response surface built using the radial basis
function (RBF) interpolation technique~\cite{buhmann2003radial} over the
samples, while $\alpha \in \R$ is a penalty constant. \RA{To prevent
  the evolution from creating} new individuals that do not belong to
$\mathbb{D}$, we impose a penalty factor $\alpha = 10$. We recall that
we minimize the opposite of the lift-to-drag coefficient.

\begin{figure}
\centering
\includegraphics[width=.9\textwidth]{figures/plot_naca_bump_functions.pdf}
\caption{NACA 4412 profile with the $5$ shape functions $r_i$ rescaled
  by a factor equal to $0.2$.\label{fig:bumps}}
\end{figure}

\cref{fig:optnaca} reports the evolution of the best-fit individual
over $10$ generations. Also in this case, we apply the
proposed algorithm and the standard GA to $25$ different initial settings, using
an initial population size $N_0 = 20$ and selecting at each generations the $N =
10$ best-fit individuals for the offspring.
The plot depicts the mean best-fit individual with solid lines, whereas
the shaded areas show the interval between the minimum and maximum (of the $25$
runs) for each generation. Even if the dimension of the parameter space
is not very high ($10$), we can see that on average the proposed algorithm is
able to converge faster. The difference between the two
methods \RA{is not as remarkable} as in a higher dimensional test case, but we can see
that the best run using standard GA is slightly worse than the mean optimum
achieved by ASGA. \RA{This again demonstrates the value in the
  proposed method.} Moreover, we \RA{emphasize} that also in this case the
decay of the objective function in the first generations with ASGA is faster.

\begin{figure}
\centering
\input{sections/plot_rbf.tex}
\caption{Results of the optimization of the NACA airfoil design in a
  $10$-dimensional space. We compare the standard GA (in blue square dots) with
        the proposed algorithm ASGA (in red circle dots) using an initial population of size $20$, while
	the dimension for each generation is fixed to $10$. The solid lines
	represent the mean, over $25$ runs, of the objective function
        corresponding to the best individual at each generation. The shaded areas show
	the interval between minimum and maximum (blue with lines for
        GA, red for ASGA).\label{fig:optnaca}}
\end{figure}

config: arxiv


text:
(*  Author:     Gertrud Bauer, Tobias Nipkow
*)

section\<open>Subdividing a Face\<close>

theory FaceDivision
imports Graph
begin

definition split_face :: "face \<Rightarrow> vertex \<Rightarrow> vertex \<Rightarrow> vertex list \<Rightarrow> face \<times> face" where
 "split_face f ram\<^sub>1 ram\<^sub>2 newVs \<equiv> let vs = vertices f;
     f\<^sub>1 = [ram\<^sub>1] @ between vs ram\<^sub>1 ram\<^sub>2 @ [ram\<^sub>2];
     f\<^sub>2 = [ram\<^sub>2] @ between vs ram\<^sub>2 ram\<^sub>1 @ [ram\<^sub>1] in
     (Face (rev newVs @ f\<^sub>1) Nonfinal,
     Face (f\<^sub>2 @ newVs) Nonfinal)"

definition replacefacesAt :: "nat list \<Rightarrow> face \<Rightarrow> face list \<Rightarrow> face list list \<Rightarrow> face list list" where
 "replacefacesAt ns f fs F \<equiv> mapAt ns (replace f fs) F"

definition makeFaceFinalFaceList :: "face \<Rightarrow> face list \<Rightarrow> face list" where
  "makeFaceFinalFaceList f fs \<equiv> replace f [setFinal f] fs"

definition makeFaceFinal :: "face \<Rightarrow> graph \<Rightarrow> graph" where
 "makeFaceFinal f g \<equiv>
     Graph (makeFaceFinalFaceList f (faces g))
           (countVertices g)
           [makeFaceFinalFaceList f fs. fs \<leftarrow> faceListAt g]
           (heights g)"

definition heightsNewVertices :: "nat \<Rightarrow> nat \<Rightarrow> nat \<Rightarrow> nat list" where
 "heightsNewVertices h\<^sub>1 h\<^sub>2 n \<equiv> [min (h\<^sub>1 + i + 1) (h\<^sub>2 + n - i). i \<leftarrow> [0 ..< n]]"

definition splitFace
 :: "graph \<Rightarrow> vertex \<Rightarrow> vertex \<Rightarrow> face \<Rightarrow> vertex list \<Rightarrow> face \<times> face \<times> graph" where
 "splitFace g ram\<^sub>1 ram\<^sub>2 oldF newVs \<equiv>
     let fs = faces g;
     n = countVertices g;
     Fs = faceListAt g;
     h = heights g;
     vs\<^sub>1 = between (vertices oldF) ram\<^sub>1 ram\<^sub>2;
     vs\<^sub>2 = between (vertices oldF) ram\<^sub>2 ram\<^sub>1;
     (f\<^sub>1, f\<^sub>2) = split_face oldF ram\<^sub>1 ram\<^sub>2 newVs;
     Fs = replacefacesAt vs\<^sub>1 oldF [f\<^sub>1] Fs;
     Fs = replacefacesAt vs\<^sub>2 oldF [f\<^sub>2] Fs;
     Fs = replacefacesAt [ram\<^sub>1] oldF [f\<^sub>2, f\<^sub>1] Fs;
     Fs = replacefacesAt [ram\<^sub>2] oldF [f\<^sub>1, f\<^sub>2] Fs;
     Fs = Fs @ replicate |newVs| [f\<^sub>1, f\<^sub>2] in
     (f\<^sub>1, f\<^sub>2, Graph ((replace oldF [f\<^sub>2] fs)@ [f\<^sub>1])
                        (n + |newVs| )
                        Fs
                        (h @ heightsNewVertices (h!ram\<^sub>1)(h!ram\<^sub>2) |newVs| ))"

primrec subdivFace' :: "graph \<Rightarrow> face \<Rightarrow> vertex \<Rightarrow> nat \<Rightarrow> vertex option list \<Rightarrow> graph" where
  "subdivFace' g f u n [] = makeFaceFinal f g"
| "subdivFace' g f u n (vo#vos) =
     (case vo of None \<Rightarrow> subdivFace' g f u (Suc n) vos
         | (Some v) \<Rightarrow>
            if f\<bullet>u = v \<and> n = 0
            then subdivFace' g f v 0 vos
            else let ws = [countVertices g  ..< countVertices g + n];
            (f\<^sub>1, f\<^sub>2, g') = splitFace g u v f ws in
            subdivFace' g' f\<^sub>2 v 0 vos)"

definition subdivFace :: "graph \<Rightarrow> face \<Rightarrow> vertex option list \<Rightarrow> graph" where
"subdivFace g f vos \<equiv> subdivFace' g f (the(hd vos)) 0 (tl vos)"

end

subset_name: curated