03.10.2016  Methodologies and Application  Ausgabe 3/2018 Open Access
CSPSO: chaotic particle swarm optimization algorithm for solving combinatorial optimization problems
 Zeitschrift:
 Soft Computing > Ausgabe 3/2018
1 Introduction
2 Related work
3 Chaotic particle swarm optimization algorithm
3.1 Basic idea

Most PSO algorithms are only suitable for one particular scenario, and they are not universal.

Most PSO algorithms are not based on multiobjective, or do not provide a personalized interface. So, they cannot effectively solve discrete, multiobjective, and personalized combinatorial optimization problems.

With the increasing of the particle dimension, the requirements of storage space and computation time will grow exponentially, which will lower the efficiency when solving the highdimensional combinatorial optimization problem.
3.2 Chaos search method
3.3 Model of combinatorial optimization problem

i is the index of category,

j is the index of item,

m is the total number of categories,

\(n_i\) is the total number of items in the ith category,

\(w_{i,j}\) is the weight of the jth item in the ith category,

\(c_{i,j}\) is the cost of the jth item in ith category.

O is the object cost, which means the manufacturing cost shall not exceed the object cost and the quality of the product shall be the optimal; \(x_{i,j} \in \{0, 1\}, \forall i\) is the mapping value of the item.
3.4 Chaos initialization
3.5 Chaos perturbing

i is the number of particle,

j is the index of position \(X_{i}(t)\),

\(x_{i,j}\) is the variable with index j from the ith current position,

\(x_{i,j}^\mathrm{p}\) is the variable with j from the ith local best position,

\(x_{i,j}^\mathrm{g}\) is the variable with j from the global best position,

\(C(x_{i,j})\) is a perturbing function of \(x_{i,j}\) with j from the position of particle i, and finally,

\(J(x_{i,j}^\mathrm{p})\) and \(J(x_{i,j}^\mathrm{g})\) are simple assessments based on the process initialization.
implies that \(x_{i,j}\) is associated with the chaotic variable \(k_{i,h}\).“If \(\displaystyle {j \ge \sum _{i=0}^{h1}N_{i} \quad \text{ and } \quad j < \sum _{i=0}^{h}N_{i}}\)”
3.6 Design of the fitness function
3.7 Pseudocodes of CSPSO
4 A CSPSO application: a healthy diet scheme
4.1 Prototype of the system
Figure  Standard  Related disease risk 

Thinness 
\({<}18.5\)
 Risk of developing problems such as nutritional deficiency and osteoporosis 
Regular  18.5–22.9  Low risk (healthy range) 
Overweight 
\({\ge } 23\)
 Moderate risk of developing heart 
Obesity  23–24.9  Disease, high blood pressure, stroke 
Obesity—class I  25–29.9  Diabetes 
Obesity—class II 
\({\ge } 30\)
 High risk of developing heart disease 
Obesity—class III 
\({\ge } 40\)
 High blood pressure, stroke, diabetes 

MainActivity is the main interface of Friend for users to input their personal physiological data,

StandardInfo and DBManager select the appropriate personalized standard values of calories and nutrients from the database,

RecommActivity is an activity, which receives the personalized data from the interface of MainActivity, and the recommended diet scheme will show in this activity,

BF_PSO is a class, which is mainly used for the initialization of the diet particles,

Agent is a class, which is mainly used for updating of the diet particles,

Finally, FoodInfo and DBManager are responsible for selecting the recommended diet from the database.
5 Experiments and performance analysis
5.1 Diversity
Scheme  Food items  Amount of food  Calories (Kcal) 

1  Watermelon  250.0 g  35 
Yoghurt (brand A)  100.0 g  63  
Pure milk (brand A)  460 ml  258  
Yoghurt (brand B)  200.0 g  184  
2  Sweet potato  300.0 g  267 
Cucumber  130.0 g  18  
Orange  182.0 g  61  
Grapefruit  139.0 g  44  
Strawberry  500.0 g  150  
3  Dumpling  100 g  250 
Watermelon  250.0 g  35  
Orange  200.0 g  70  
Grape  500.0 g  185 
Scheme  Food items  Amount of food  Calories (Kcal) 

1  Noodle  100 g  284 
Peach  200.0 g  83  
Milk (brand B)  250.0 ml  173  
2  Dumpling  100 g  253 
Cherry  500.0 g  200  
Yoghurt (brand B)  100.0 ml  87  
3  Chinese style baked roll  80 g  234 
Grape  500.0 g  185  
Milk (brand C)  200.0 ml  173 
5.2 Iteration times
HLRPSO  Times  Times  Times  Times  Times  Average 

1–5  34  17  12  13  26  15.1 
6–10  16  12  23  9  10  
11–15  22  12  10  16  10  
16–20  11  10  18  9  12 
HLRPSO  Times  Times  Times  Times  Times  Average 

1–5  3  4  6  4  4  4.1 
6–10  4  5  6  2  4  
11–15  3  2  4  5  4  
16–20  4  4  4  5  5 
5.3 Ergodicity
HLRPSO  1  2  3  4  5  6  7  8  9  10 

Staple  31  30  31  30  30  30  30  30  21  15 
Fruits  20  30  20  30  30  30  30  30  28  28 
Milk  30  25  30  25  25  25  25  25  30  29 
11  12  13  14  15  16  17  18  19  20  

Milk  29  30  25  29  30  30  30  25  30  29 
Staple  32  31  30  32  31  22  22  30  31  32 
Fruits  28  20  30  28  20  28  28  30  20  28 
CSPSO  1  2  3  4  5  6  7  8  9  10 

Staple  4  2  23  1  2  7  4  14  14  30 
Fruits  26  29  15  29  29  4  26  19  21  30 
Milk  6  9  25  29  9  27  10  24  26  25 
11  12  13  14  15  16  17  18  19  20  

Staple  16  25  31  5  32  24  7  4  2  24 
Fruits  7  28  20  1  28  12  4  26  7  12 
Milk  27  19  30  16  29  30  27  6  30  30 