A novel algorithm for generating minimum energy points from identically charged particles in 1D, 2D and 3D unit hypercubes

Abstract

Generating minimum energy points (MEPs) is an optimal solution of many real-world problems, such as the selection of best locations for hospitals inside a city that reduce the overcrowding and competition and avoid the less-populated regions. The key idea is considering these locations as charged particles with the same sign (i.e., repel each other) inside a box and distribute these points by minimizing the total electric potential energy (TEPE) among them. The practice demonstrated that most of the existing techniques for generating MEPs are complex, especially for non-mathematicians. Therefore, the greedy algorithm (GreA) is the classical widely used algorithm for its simplicity even though a satisfactory result is not guaranteed. This paper gives a novel algorithm for generating MEPs from identically charged particles in 1D, 2D and 3D unit hypercubes. The results show that the new algorithm distributes the points far away from each other to reduce the TEPE of the generated MEPs more effectively than the GreA. The new algorithm is a significant improvement of the GreA to overcome its unsatisfactory results. Therefore, the new algorithm in its current form or after some improvements is highly recommended to be used instead of the GreA for many different applications.

Keywords:

• DEoptim
• Electric field lines
• Electric potential energy
• Equipotential circles
• GenSA
• Greedy algorithm
• Minimum energy points
• PSO
• Representative points

Mathematical Subject Classification:

• 1.00940
• 1.00950
• 1.00990

Acknowledgments

The authors thank the two referees and the Editor Prof. Narayanaswamy Balakrishnan for constructive comments that lead to significant improvement of this paper.

Additional information

Funding

This work was partially supported by the BNU-HKBU United International College Research Grants (Nos. R201810, R201912 and R202010) and the Zhuhai Premier Discipline Grant.