Geometric Constraint Solving Based on Cell Membrane Optimization

INTRODUCTION

---

The parametric design is a geometric constraint-solving problem. Geometric constraint solving approaches are made of three approaches: algebraic-based solving approach based solving approach and graph-based solving approach (Bo, 1999). One constraint describes a relation that should be satisfied. Once a user defines a series of relations, the system will satisfy the constraints by selecting proper state after the parameters are modified. The idea is named model-based constraints. Constraint solver is a segment for the system to solve the constraints.

In the recent decades, it has seen many new optimization algorithms about the global optimization. For example, Genetic algorithms was put forward by simulating the natural selection of Darwin's biological evolution theory and the biological evolution of genetic mechanism (Holland, 1975). Ant colony optimization algorithm was inspired by ant foraging (Colorni et al., 1991). PSO was put forward by simulating the flight behavior of birds (Kennedy and Eberhart, 1995). In order to achieve optimization, the Artificial Fish School Algorithm constructed artificial fish to imitate the fish feeding, clusters, rear-end and random behaviors (Xiaolei, 2003). Leapfrog algorithm was proposed through the simulation of the frogs’ feeding characteristics (Eusuff and Lansey, 2003). Migration algorithm is simulated the migration mechanism-population is transferred with the economic center of gravity and is spread with the increasing population pressure to achieve global optimization (Zhou and Mao, 2003). Colony algorithm is proposed mainly based on the characteristics of bees seeking nectar (Karaboga, 2005).

This paper studies the characteristics of the cell membrane and its material transfer methods, from which construct optimization model. Combined with the basic idea of global optimization algorithms, we propose a new global optimization algorithm optimization as Cell Membrane Optimization (Tan and Yu, 2011).

CELL MEMBRANE OPTIMIZATION

According to the process of membrane transport material, the material is divided into three types: fat-soluble substances, high concentrations non-fat-soluble material (HS) and low concentrations non-fat-soluble material (LS) in this paper. In solving optimization problems, a material is corresponding to a solution of the optimization problem, the three different types material are corresponding to three solutions which of different characteristics.

This paper studies is for the unconstrained function optimization problem, as form (1) described.

(1)

In it:

Suppose form (1) always has solution, i.e., the global optimum exists. The overall process of Cell Membrane Optimization (CMO) is as follows.

Initial the material: In the solution space:

Randomly generated m n-dimensional material, every material are randomly distributed in the solution space, calculate the value of their function and keep the best material in the X^best.

Classified material type: First, the function value of each material sorted from small to large, material at the top Ps percentage is divided into fat-soluble substance, the material at the back is classified as non-fat-soluble substances; and then the non-fat-soluble material is further divided into two types: high concentration and low concentration. For a substance Y, the concentration of which is defined as the percentage of the material contained in the neighborhood for the total number of the material. As form (2) shows:

(2)

where, n means the number of the material of Xⁱ (i=1, …, m) whose distance from the Y is less than rx(u - l) (it is for any k, with):

The average of all concentration is MeanCon, as form (3) shows:

(3)

Free diffusion of fat-soluble substances: If f (newfsXⁱ) is better than (fsXⁱ), then use newfsXⁱ to replace fsXⁱ. Then shrink the search radius vector: Radius₁ = Radius₁xPb, repeat this process until max {Radius_1k,∀k}>Pa. At the start, the calculate method of the search radius Radius₁ is shown in form (4):

(4)

The correct method of search range is that for k, if newfsX_kⁱ>u_k, then newfsX_kⁱ = u_k; if newfsX_kⁱ<l_k, then newfsX_i^k= l_k. The scope correction of the new material appeared below use the same method, no specific description.

High concentrations non-fat-soluble substances diffusion: Assuming that the probability that each high concentrations non-fat-soluble existences carrier is same, set the probability is P_c1, if the randomly generated number rand()≤P_c1, rand() is between 0 and 1; then the substance (such as hsXⁱ) can help the movement to spread from high concentration to low concentration side and to make the new location as the local search center (denoted hsXCⁱ); otherwise make the original place as the local search center. Then, the substance will do locn times local search campaign. Before this the search radius vector Radius2 need to be initialized. The method shown in form (5):

(5)

Then made locn times random movement (that is generate locn material) in the search area where hsXCⁱ as the center and Radius₂ as radius and corrected their search area. Record the optimal material besthsXⁱ of the locn material. If f (besthsXⁱ)< f(hsXCⁱ), then use besthsXⁱ to replace hsXⁱ, or use hsXCⁱ to replace hsXⁱ.

Low concentrations non-fat-soluble substances diffusion: Assuming that the probability that each low concentrations non-fat-soluble existences carrier is same, set the probability is P_c2. Every low concentrations non-fat-soluble owns energy and the energy value is in [0, 1]. First calculated the function value f (lsX ⁱ) (i = 1, ..., m3) for each low concentrations non-fat-soluble substances, then sort the function value from small to large. For the material that has the minimum function value, its energy Eⁱ is E_min, For the material that has the largest function value, its energy Eⁱ is E_max, the energy Eⁱ of other substances is between E_min and E_max and is calculated with a linear order. Which, E_min and E_max is the constant in [0, 1], here, E_min is equal to 0, E_max is equal to 1.

If a substance (such as lsXⁱ) carrier and there is enough energy, then it can be active transport, from the low concentration side to the high concentration side and to make a new location to be the center of the local search (denoted lsXCⁱ), or the original place to be the local search center. After the active transport, the new location (lsXⁱ) of the low concentrations non-fat-soluble substances (lsXCⁱ) is shown in form (6):

(6)

Then, initial the search radius vector Radius₃, as is shown in form (7):

(7)

Then made locn times random movement (that is generate locn material) in the search area where lsXCⁱ as the center and Radius₃ as radius and corrected their search area. Record the optimal material bestlsXⁱ of the locn material. If f(bestlsXⁱ)< f(lsXCⁱ), then use bestlsXⁱ to replace lsXⁱ, or use lsXCⁱ to replace lsXⁱ.

Update the material: Use the new material group that composed by the fat-soluble substances, high concentration non- fat-soluble substances and low concentrations non-fat-soluble substances to replace the old material groups Xⁱ (i=1, …, m).

GEOMETRIC CONSTRAINT SOLVING

The constraint problem can be formalized a7s (E, C) (Sheng-Li et al., 2003), here E = (e₁, e₂, ……, e_n), it can express geometric elements, such as point, line, circle, etc; C = (c₁, c₂, …, c_m), c_i is the constraint set in these geometric elements. Usually one constraint is represented by an algebraic equation, so the constraint can be expressed as follows:

(8)

X = (x₀, x₁, …, x_n), X_i are some parameters. Constraint solving is to get a solution x to satisfy formula (8):

(9)

Apparently, if X_j can satisfy F (X_j) = 0, then X_j can satisfy formula (8). So the constraint problem can be transformed to an optimization problem and we only need to solve min (F ( X_j ) )<ε.ε is a threshold.

APPLICATION INSTANCE

In CMO, there are eight adjustable parameters: the maximum iteration generation G is generally in [10, 100]; the local search time locn of no-fat-soluble substance is generally in [10, 100]; Material total quantity m is generally in [10, 50]; the percentage in the colony of fat-soluble substances Ps is generally in [0.1, 0.3]; the threshold to stop thread of fat soluble substance Pa is generally in [1e-6, 1e-3]; the constringency rate of search radius is in [0.8, 0.99]; High and low concentration no-fat-soluble substance in a carrier P_c1, P_c2 is generally in [0.2, 0.8]. The radius r for substance concentration for an algorithm performance is less affected, can be set as a constant. It is not included in the programmable parameters, is generally in [0.2, 0.5].

The two graphs in Fig. 1 are drafts in engineering design. Figure 1b is an auto-produced graph after some sizes of the Fig. 1a are modified by CMO. In this instance, the parameters are set G = 20, locn = 10, m = 20, Ps = 0.2, Pa = 1e-5, Pb = 0.9, P_c1 = 0.8, P_c2 = 0.5, r = 0.4, respectively.

Fig. 1(a,b):	(a) A design instance (b) Solving result

From the Fig. 1 we can realize from the above figures that once a user defines a series of relations, the system will satisfy the constraints by selecting proper state after the parameters are modified by CMO.