![](https://csdnimg.cn/release/download_crawler_static/15470353/bg4.jpg)
Computational Intelligence and Neuroscience
e rst slight improvement is that we get rid of sorting
of the items according to the tness value which will decrease
in time cost.
e second improvement is that we adopt a new frog
individual position update formula instead of the rst two
frog leapings. e idea is inspired by the DE/Best//Bin in DE
algorithm. Similarly, each frog individual is represented as a
solution X
𝑖
andthenthenewsolutionis given by
=
𝑔
±
2
×
𝑘
−
𝑝1
, ()
where
𝑔
is the current global best solution found so far.
𝑘
is the best solution of the kth memeplex.
𝑝1
is an individual
of random selection with index of 1 =and
2
is random
number uniformly distributed in [0,1].Inparticulartheplus
or minus signs are selected with certain probability. e main
purpose of improvement in () is to quicken convergence
rate.
e third improvement is to randomly generate new
individuals with certain probability instead of unconditional
generating new individuals, which takes into consideration
the retention of the better individuals in the population.
e main step of ISFLA is given in Algorithm .In
Algorithm , P is the size of the population. M is the number
of memeplex. D is the dimension of decision variables. And
1
is a random real number uniformly distributed in (, ).
And
2
,
3
,
4
,and
𝑚
are all D-dimensional random vectors
and each dimension is uniformly distributed in (, ). In
particular,
𝑚
is called probability of mutation which controls
the probability of individual random initialization.
3.4. e Frame of CSISFLA. In this section, we will demon-
strate how we combine the well-designed ISFLA with L
´
evy
ights to form an eective CSISFLA. e proposed algorithm
does not change the main search mechanism of CS and
SFLA. In the iterative process of the whole population, L
´
evy
ights are rstly performed and then frog-leaping operator is
adopted in each memeplex. erefore, the strong exploration
abilities in global area of the original CS and the exploitation
abilities in local region of ISFLA can be fully developed. e
CSISFLA architecture is explained in Figure .
3.5. CSISFLA Algorithm for 0-1 Knapsack Problems. rough
thedesignabovecarefully,thepseudocodeofCSISFLAfor-
knapsack problems is described as follows (see Algorithm ).
It can be analyzed that there are essentially three main
processes besides the initialization process. Firstly, L
´
evy
ights are executed to get a cuckoo randomly or generate
a solution. e random walk via L
´
evy ights is much more
ecient in exploring the search space owing to its longer
step length. In addition, some of the new solutions are
generated by L
´
evy ights around the best solution, which
can speed up the local search. en ISFLA is performed in
order to exploit the local area eciently. Here, we regard
the frog-leaping process as the process of cuckoo laying egg
in a nest. e new nest generated with a probability
𝑚
is
far enough from the current best solution, which enables
CSISFLA to avoid being trapped into local optimum. Finally,
when an infeasible solution is generated, a repair procedure
is adopted to keep feasibility and, moreover, optimize the
feasible solution. Since the algorithm can well balance the
exploitation and exploration, it expects to obtain solutions
with satisfactory quality.
3.6. Algorithm Complexity. CSISFLA is composed of three
stages: the sorting by value-to-weight ratio, the initialization,
and the iterative search. e quick sorting has time complex-
ity (log ()). e generation of the initial cuckoo nests has
time complexity (×).eiterativesearchconsistsoffour
steps (comment statements in Algorithm ), and so forth,
the L
´
evy ight, the rst frog leaping, generate new individual
and random selection which costs the same time ().In
summary, the overall complexity of the proposed CSISFLA is
(log ())+(×)+()=(log ())+(×).
It does not change compared with the original CS algorithm.
4. Simulation Experiments
4.1. Experimental Data Set. In existent researching les,
cases studies and research of knapsack problems are about
small-scale to moderate-scale problems. However, in real-
world applications, problems are typically large-scale with
thousands or even millions of design variables. In addition,
the complexity of KP problem is greatly aected by the
correlation between prots and weights [–]. However,
few scholars pay close attention to the correlation between
the weight and the value of the items. To test the validity
of the algorithm for dierent types of instances, we adopt
uncorrelated, weakly correlated, strongly correlated, multiple
strongly correlated, prot ceiling, and circle data sets with
dierent dimension. e problems are described as follows:
(i) uncorrelated instances: the weights
𝑗
and the prots
𝑗
are random integers uniformly distributed in
[10,100];
(ii) weakly correlated instances: the weights
𝑗
are ran-
dom integers uniformly distributed in [10,100],and
the prots
𝑗
are random integer uniformly dis-
tributed in [
𝑗
−10,
𝑗
+10];
(iii) strongly correlated instances: the weights
𝑗
are
random integers uniformly distributed in [10,100]
and the prots
𝑗
are set to
𝑗
+10;
(iv) multiple strongly correlated instances: the weights
𝑗
are randomly distributed in [10,100].Iftheweight
𝑗
isdivisibleby,thenwesetthe
𝑗
=
𝑗
+30otherwise
set it to
𝑗
=
𝑗
+20;
(v) prot ceiling instances: the weights
𝑗
are randomly
distributed in [10,100] and the prots
𝑗
are set to
𝑗
=3
𝑗
/3;
(vi) circle instances: the weights
𝑗
are randomly dis-
tributed in [10,100]and the prots
𝑗
are set to
𝑗
=
4
2
−(
𝑗
−2)
2
.Choosing=2/3, =10.
Foreachdataset,wesetthevalueofthecapacity.
Consider =0.75∑
𝑛
𝑗=1
𝑗
.