
provide specific values for the 
multiplicative constants, i.e. $\frac{32}{\delta^2}$ and 
$\frac{32(1+\varepsilon)}{\delta^2\gamma_0}$ for the terms 
$n\lambda\log \lambda$ and $n^2$, respectively 
(see Step 5 in Theorem~\ref{thm:pbil-on-los}).  
Moreover, 
the result also matches the runtime bound of 
the \umda on \los for 
a small population $\lambda=\bigTheta{\log n}$ 
\cite{Dang:2015:SRA:2739480.2754814}.

Note that Theorem~\ref{thm:pbil-on-los} requires some condition
on the selective pressure, that is
$\gamma_0 \le \frac{\eta^{\ceil{\xi}+1}}{(1+\delta)e}$ 
where $\xi = \frac{\ln p_0}{p_0-1}$ 
and $p_0:=\frac{\gamma_0}{1+\varepsilon}$  
for any positive constants $\delta, ~\varepsilon$
and smoothing parameter $\eta \in (0,1]$. Although for 
practical applications, we have to address
these constraints to find a suitable set of values for $\gamma_0$, 
this result here tells us that there exists some settings 
for the \pbil such that it can optimise \los 
within $\bigO{n\lambda\log \lambda+n^2}$ time in expectation.

\section{Runtime Analysis of the \pbil on \bval}
\label{sec:pbil-binval}
We first partition the search space into non-empty disjoint subsets $A_0,\ldots,A_n$.

\begin{lemma}\label{bval-los-similarity}
	Let us define the levels as  
	$$
	A_j :=\bigg\{ x\in \{0,1\}^n\bigg| \sum_{i=1}^j 2^{n-i} \le \bval(x) < \sum_{i=1}^{j+1} 2^{n-i}\bigg\},
	$$
	for $j \in [n]\cup\{0\}$, where $\sum_{i=1}^{0}2^{n-i}=0$.
	If a bitstring $x$ has exactly $j$ leading ones, i.e.
    $\los(x)=j$, then $x\in A_j$. 
\end{lemma}
\begin{proof}
	Consider a bitstring $x=1^j0\{0,1\}^{n-j-1}$. 
	The fitness  contribution of the first $j$ leading ones to $\bval(x)$ is
	$\sum_{i=1}^{j}2^{n-i}$. The $(j+1)$-th 
	bit has no contribution, while that of the last
	$n-j-1$ bits ranges from zero to 
	$\sum_{i=j+2}^{n}2^{n-i}=\sum_{i=0}^{n-j-2}2^{i} = 2^{n-j-1}-1$.
	So overall,
$	\sum_{i=1}^{j}2^{n-i} \le \bval(x) \le \sum_{i=1}^{j+1}2^{n-i}-1 < \sum_{i=1}^{j+1}2^{n-i}.
$
Hence, the bitstring $x$ belongs to level $A_j$. 
\end{proof}

In both problems, all that matters to determine 
the level of a  bitstring is the position of the first 0-bit 
when scanning from the most significant to the least significant bits.
Now consider two bitstrings in the same level for \bval, 
their rankings after the population is sorted are also determined 
by some other less significant bits; however, the proof of 
Theorem~\ref{thm:pbil-on-los} never takes these bits into account.
Thus, the following corollary yields the first 
upper bound on the expected optimisation time of the \pbil 
and the \umda (when $\eta=1$) for \bval. 

\begin{corollary}\label{thm:pbil-on-bval}
The \pbil with margins and offspring population size
	$\lambda \ge c\log n$ for a sufficiently large constant $c>0$,
	parent population size $\mu =\gamma_0\lambda$ for any constant
    $\gamma_0$ satisfying 
    $\gamma_0 \le \eta^{\ceil{\xi}+1}/((1+\delta)e)$ 
    where $\xi = \ln (p_0)/(p_0-1)$ and $p_0:=\gamma_0/(1+\varepsilon)$  
    for any positive constants $\delta, ~\varepsilon$
    and smoothing parameter $\eta \in (0,1]$, 
	has expected optimisation time $\bigO{n\lambda\log \lambda +n^2}$
	on \bval.
\end{corollary}

\section{Conclusions}
\label{sec:conclusion}
Runtime analyses of \edas are scarce. Motivated by this, we have derived 
an upper bound of $\bigO{n\lambda\log \lambda + n^2}$ on
the expected optimisation time 
of the \pbil on both \los and \bval
for a population size $\lambda=\bigOmega{\log n}$. 
The result improves upon the previously best-known bound 
$\bigO{n^{2+\varepsilon}}$ from \cite{bib:Wu2017}, and requires 
a much smaller population size $\lambda=\bigOmega{\log n}$, and
uses relatively straightforward arguments. 
We also presents the first upper 
bound on the expected optimisation time 
of the \pbil on \bval. 

Furthermore, our analysis demonstrates that the level-based theorem 
can yield runtime bounds for \edas 
whose models are updated using information gathered from
the current and previous generations. An additional aspect of our analysis 
is the use of the \dkw inequality to bound the true distribution by 
the empirical population sample when the number of samples is large enough. 
We expect these arguments will lead to new results in runtime 
analysis of evolutionary algorithms.

\section*{Appendix}
\begin{lemma}[\textsc{AM-GM Inequality} \cite{Steele:2004}]
\label{lem:am-gm inequality}
Let $x_1,\ldots,x_n$ be $n$ non-negative real numbers. It always holds that
$$\frac{x_1+x_2+\cdots+x_n}{n}  \ge \left(x_1\cdot x_2\cdots x_n\right)^{1/n},$$
and equality holds 
if and only if $x_1=x_2=\cdots=x_n$.
\end{lemma}

\begin{proof}[\textsc{Proof of horizontal asymptote}]
The function can be rewritten as 
$g(j)=\frac{1}{1-p_0}\cdot \frac{p_0^{1/j}-1}{1/j}$. 
Denote $t:=1/j$, we obtain 
$g(t)=\frac{1}{1-p_0}\cdot \frac{p_0^t-1}{t}$. 
Applying L'H{\^{o}}pital's rule yields:
$$
\lim_{j\to +\infty} g(j) = \lim_{t\to 0^{+}} g(t) 
= \frac{ \lim_{t\to 0^{+}} \left(p_0^t \ln p_0\right)}{1-p_0} 
=\frac{\ln p_0}{1-p_0}=-\frac{\ln p_0}{p_0-1}.
$$
\end{proof}



<gh_stars>1-10
package com.lanking.uxb.service.holiday.value;

import java.io.Serializable;
import java.math.BigDecimal;
import java.util.Date;

import com.lanking.cloud.domain.type.StudentHomeworkStatus;
import com.lanking.cloud.sdk.util.StringUtils;
import com.lanking.uxb.service.user.value.VUser;

/**
 * 学生查看寒假作业的VO
 * 
 * @author wangsenhao
 *
 */
public class VHolidayStuHomeworkItem implements Serializable {

	private static final long serialVersionUID = 5481046861342559857L;

	/**
	 * holidayStudentHomeworkItem Id
	 */
	private Long holidayStuHomeworkItemId;

	private Long holidayHomeworkId;
	/**
	 * 专项作业名称
	 */
	private String name;
	/**
	 *