Sage Journals: Discover world-class research

Abstract

To address the problems of long run times, long path length and low efficiencies of traditional intelligent algorithms to optimise free-form surface inspection path algorithms, this paper proposes a method based on an improved cuckoo search algorithm. Since the basic cuckoo search algorithm suffers from problems such as low search efficiency and the tendency to fall into local optimum solutions, the basic cuckoo search algorithm is improved by using a parameter adaptive adjustment strategy and dynamic neighbourhood search strategy, so that the improved cuckoo search algorithm can obtain the optimised inspection path stably and quickly. The local composition of the free-form surface inspection path and the corresponding mathematical model are first analysed, and then traditional intelligent algorithms and the improved cuckoo search algorithm are applied to optimise the mathematical model. The results of inspection experiments conducted with an engine impeller showed that the improved cuckoo search algorithm reduced the length of the optimised inspection path by at least 8.6%, reduced the algorithm run time by at least 35%, and improved the inspection efficiency by at least 1.2% compared to those of the genetic algorithm, simulated annealing algorithm, and ant colony Optimisation algorithm. The improved cuckoo search algorithm allows for effective free-form surface inspection path Optimisation and an improved inspection efficiency.

Keywords

Free-form surfaces path optimisation cuckoo search algorithm parameter adaptive adjustment dynamic neighbourhood search

Introduction

Free-form surface parts are widely used in various industries, such as the aerospace, automotive, moulding, biomedical and optical industries, so the inspection of the geometries and accuracies of free-form surface parts has become critical.¹ Coordinate measuring machines (CMMs) are now widely used in various industries for geometric measurement and inspection because of their high accuracy and ease of operation.² As the measurement points on a free-form surface are detected sequentially by the CMM, the point picking strategy and the measurement point path planning strategy are two important factors that affect the inspection accuracy and efficiency of the CMM. As mentioned the two factors mentioned above, the sensible sampling strategy usually requires that the smallest possible number of samples be taken on a free-form surface while ensuring inspection accuracy, as a means of improving inspection efficiency. In addition to this, inspection path planning often requires empty inspection strokes to be minimised so that the probe can traverse each inspection point without repetition, thereby improving inspection efficiency.

There are many experts and scholars who have done a lot of scientific research on the problem of path planning for free-form surface inspection. For instance, He et al.³ applied the Kuhn–Munkras algorithm for the optimisation of free-form surface inspection paths and proposed an automatic collision inspection algorithm to avoid the collision of probes, which not only ensured the safety of the inspection process but also improved the inspection efficiency. Liu et al.⁴ proposed an optimal path planning method for free-form surface dimensional feature inspection, which incorporated a dynamic search volume-based collision inspection algorithm and a local inspection path optimisation method that integrated the probe trajectory and stylus rotation. This method was experimentally verified to significantly improve the inspection efficiency of the CMM. Yi et al.⁵ proposed a comprehensive path planning method for free-form surface inspection. This method was based on a graphics processor algorithm for accelerated reachability cone calculations, which reduced the total inspection time by dividing points of the same inspection pose into a group of sequential inspections, thereby reducing the number of probe rotations. Li et al.⁶ grouped inspection points based on the relationship between the orientation and points, then applied the Lin–Kernighan algorithm to optimise the inspection path for each group, and finally applied a greedy algorithm to optimise the global inspection path. In other studies, safe and efficient inspection processes for free-form surfaces were ensured by applying collision inspection algorithms and algorithms that reduced the number of probe rotations.^3–6

Mian and Al-Ahmari⁷ Compared the results of three traditional intelligent algorithms (simulated annealing algorithm, genetic algorithm and Brutalis) to optimise the inspection path. The results showed that the simulated annealing algorithm was optimal. Chen and Shang⁸ also compared the results of three swarm intelligence algorithms (Ant Colony Optimisation, Genetic Algorithm and Particle Swarm Optimisation) to optimise free-form surface inspection paths and verified the optimal performance of the Ant Colony Optimisation algorithm by experimenting with a free-form surface sample. Stojadinovic et al.⁹ proposed a model for prismatic part inspection path planning and applied an ant colony Optimisation algorithm to optimise this model with good results, however, the model is only for prismatic part inspection path planning. Liu et al.¹⁰ applied the improved genetic algorithm for the inspection path planning of spiral bevel gear tooth surfaces and compared the proposed improved genetic algorithm with other basic intelligent algorithm simulations. The improved genetic algorithm improved the optimised path length and operation efficiency by at least one-fifth, which verified the effectiveness of this method. In other studies, the inspection path was optimised by applying the traditional intelligent algorithm to shorten the length of the inspection path, thus improving the inspection efficiency.^7–10 However, this approach was limited to small-scale measurement points. When optimising large-scale measurement points, the efficiency and accuracy of traditional intelligent algorithms for Optimisation reduced, resulting in an insufficient Optimisation effect.

The free-form surface inspection path planning problem studied in this paper is similar to the travelling salesman problem. The traveller and the city to be travelled in the travelling salesman problem correspond to the probe of the measuring machine and the set of points to be measured in the free-form surface inspection path planning, respectively. The application of intelligent algorithms is currently one of the effective ways to solve the traveller’s problem, and therefore, many scholars are conducting considerable research on traditional intelligent algorithms, such as the genetic algorithm,¹¹ particle swarm optimisation algorithm,¹² simulated annealing algorithm,¹³ and ant colony optimisation algorithm.^14,15 In addition, many other scholars have performed considerable research on new swarm intelligence optimisation algorithms. Such as the bat algorithm,^16,17 imperial competition algorithm,¹⁸ grey wolf algorithm,¹⁹ and cuckoo search algorithm.^20,21 Of these, the cuckoo search algorithm, a new type of swarm intelligence optimisation algorithm, has been applied by many scholars to optimise the travelling salesman problem.

In summary, the performance of the cuckoo search algorithm was improved in this study by adopting a parameter adaptive adjustment strategy and a dynamic neighbourhood search strategy. The basic cuckoo search algorithm was selected as the starting point, and its shortcomings, such as a low search efficiency and the tendency to fall into the local optimal solutions, were addressed. The aim of the improved cuckoo search algorithm is to enhance the performance of the basic cuckoo search algorithm, enabling the free-form surface inspection path length to be further reduced so that inspectors can inspect the free-form surface more efficiently. To verify the advantages of the improved cuckoo search algorithm to optimise free-form surface inspection paths compared to other intelligent algorithms, simulations and experiments were carried out to compare it with the genetic, simulated annealing and ant colony optimisation algorithms. An engine impeller model was selected as the experimental object, and the free-form surface measurement point inspection paths of different sizes were optimised. Other elements of this paper are arranged as follows: Section 2 introduced the mathematical model of the free-form surface inspection path to be optimised. Section 3 described the principles of the basic cuckoo search algorithm and improvement strategies for improving the cuckoo search algorithm. Section 4 analysed the results of simulation experiments and example experiments for each intelligent algorithm. Section 5 concluded the study of this paper.

Mathematical model for inspection paths

Planning the inspection path for the workpiece should be considered before inspecting it. An unreasonable inspection path not only leads to inefficient inspection, but also risks damage to the probe if it collides with the workpiece.

Therefore, the purpose of creating inspection paths is to orderly and efficiently detect the coordinates of the actual points distributed over the surface of the component. At the same time, it is ensured that no collisions occur between the probe and the workpiece or other objects during the inspection process.

The inspection path is the trajectory of the probe of the measuring machine during the inspection process, which consists of a sequence of measuring points, positioning points, retreat points and touch directions. As shown in Figure 1, the local inspection path of a free-form surface consists of three parts, namely $d_{1}$ , $d_{2}$ and $l_{1}$ .

Figure 1.

Schematic diagram of local inspection of probe.

As can be seen from Figure 1, the probes are inspected in the following order:

P_{p, i} \to P_{i} \to P_{r, i} \to P_{p, i + 1} \to P_{i + 1} \to P_{r, i + 1},

where $P_{i}$ and $P_{i + 1}$ are the measurement points, that is, the points of contact between the probe of the measuring machine and the surface of the part. $P_{p, i}$ and $P_{p, i + 1}$ are positioning points, that is, the points used by the measuring machine probe to position the measurement point. $P_{r, i}$ and $P_{r, i + 1}$ are retreat points, which are spatial points in close proximity to the measurement points. $P_{p, i}$ and $P_{r, i}$ can be represented as follows:

{\begin{matrix} P_{d, i} = P_{i} + {\vec{n}}_{i} d_{1} \\ P_{t, i} = P_{i} + {\vec{n}}_{i} d_{2} \end{matrix},

(1)

where ${\vec{n}}_{i}$ , $d_{1}$ and $d_{2}$ represent the normal vector, positioning distance and retreat distance of measurement point $P_{i}$ respectively. For each inspection, the positioning distance $d_{1}$ and retreat distance $d_{2}$ are specified according to the mechanical characteristics of the measuring machine and the experience of the technician, both of which are constants. It follows that $l_{1}$ is the main factor determining the inspection time when inspecting two adjacent measurement points. The length of the path of the probe movement for the CMM inspection of measurement point $P_{i}$ and measurement point $P_{i + 1}$ in Figure 1 is represented as follows:

d = d_{1} + d_{2} + l_{1},

(2)

where $d_{1}$ represents the distance of the probe’s movement from retreat point $P_{r, i}$ to the positioning point $P_{p, i + 1}$ .

Therefore, by analysing the local inspection path of the free-form surface, the global inspection path can be introduced. Assuming that there are n points to be measured on a free-form surface, the total path length of the probe motion is represented as follows:

D = (d_{1} + d_{2}) n + \sum_{i = 1}^{n - 1} l_{i},

(3)

where $l_{i} (i = 1, 2, 3, . . ., n - 1)$ represents the distance that the probe moves from the retreat point of the ith measurement point to the positioning point of the i + 1st measurement point. From equation (3), it can be seen that since the positioning distance $d_{1}$ and the retreat distance $d_{2}$ are constant values, the length of $l_{i}$ needs to be as short as possible if one wants to obtain a total detection path that is as short as possible. The objective function required for $l_{i}$ optimisation in this paper is therefore represented as follows:

L = \sum_{i = 1}^{n - 1} l_{i} = \sum_{i = 1}^{n - 1} \sqrt{{(x_{i + 1} - x_{i})}^{2} + {(y_{i + 1} - y_{i})}^{2} + {(z_{i + 1} - z_{i})}^{2}},

(4)

where $(x_{i}, y_{i}, z_{i})$ and $(x_{i + 1}, y_{i + 1}, z_{i + 1})$ represent the retreat point coordinates of the ith measurement point and the positioning point coordinates of the i + 1st measurement point, respectively.

Inspection path optimisation using improved cuckoo search algorithm

Cuckoo search algorithm

The cuckoo search (CS) algorithm is a novel swarm intelligence optimisation algorithm proposed by British scholars Yang and Deb in 2009.²² The CS algorithm simulates the breeding behaviour of the cuckoo. The most specific habit of the cuckoo is the parasitic nesting of eggs. As cuckoos have no incubation behaviour of their own, some cuckoos in nature lay their own eggs in parasitic nests, relying on the host birds to incubate and raise their chicks. In order to not to be detected by the host bird, the cuckoo will remove one or several eggs from the host bird before laying their own eggs, so that the number of eggs in the nest is equal or similar. When the host bird finds unfamiliar eggs in the nest, the host bird will discard the eggs laid by the cuckoo, or simply re-nest. The CS algorithm efficiently solves optimisation problems by simulating the parasitic breeding behaviour of the cuckoo. One of the most important mechanisms in the CS algorithm is the Levy flight, a strategy that allows the CS algorithm to efficiently obtain a globally optimal solution. Levy flights are subject to the Levy probability distribution, that is, the search path consists of multiple short jumps with few occurrences of long jumps. This type of search allows the CS algorithm to have a larger search space and improves the CS algorithm’s ability to jump out of local optimal solutions. In addition, by defining the probability of the cuckoo eggs being found by the host bird, the poorer eggs that are not adapted to the environment are eliminated, and the better eggs that are adapted to the environment are hatched, ensuring that the CS population is made up of good individuals and making the CS algorithm highly convergent.

There are several idealised rules in the CS algorithm:

(1) Each cuckoo can only lay one egg at a time, except that a nest is chosen at random to incubate the eggs it lays.

(2) The best nests and the highest quality eggs are preserved for future generations.

(3) The number of host nests is fixed, and host birds will find exotic eggs with a probability of Pa ∈ [0,1].

The CS paths and locations based on the above three idealised rules are updated as follows:

X_{i}^{t + 1} = X_{i}^{t} + α \oplus Levy (s, λ),

(5)

Where $X_{i}^{t}$ in represents the ith solution in the tth generation, α represents the step size and α > 0, ⊕ represents two points being multiplied, and Levy(s, λ) represents a random search path and obeys the Levy probability distribution.

The steps of the CS algorithm are as follows:

Step 1: Set the algorithm parameters: population size pop, discovery probability Pa, and maximum number of iterations N_max.

Step 2: Initially calculate the fitness value g(x) and update the current optimal nest location and optimal solution.

Step 3: Determine whether the set maximum number of iterations is reached, and if so, output the global optimal solution. If not, generate candidate solution y using Levy flight.

Step 4: Calculate the fitness value g(y) of the candidate solution y. If the fitness value g(y)>g(x), use the candidate solution y to replace the original solution x.

Step 5: Round off poor solutions according to the probability of discovery Pa.

Step 6: Update the current optimal nest location and optimal solution.

Step 7: Determine if the set maximum number of iterations has been reached, and if so, output the optimal nest and the global optimal solution. If not, repeat Steps 3–6.

Improved cuckoo search algorithm

Neighbourhood structure

The adaptive dynamic neighbourhood hybrid cuckoo search (ADNHCS) algorithm uses three different neighbourhood structures, the 2-opt neighbourhood, the 3-opt neighbourhood structure, and the double-bridge neighbourhood structure. In this paper, we will take eight measurement points as an example and assume that the initial solution is X = (a, b, c, d, e, f, g, h). The three different neighbourhood structures mentioned above and the recombination paths for different neighbourhoods are described below.

2-opt neighbourhood structure

The 2-opt neighbourhood structure, which cuts off two sub-paths and then restructures the connection, is also known as the ‘inverse order operator’. As shown in Figure 2, the two sub-paths b-c and g-h in the initial path are selected to cut them off, and then a new path X1 is obtained by swapping and restructuring the connection, that is, by reversing the path connection between measurement points b and h. The candidate solution X1 = (a, b, g, f, e, d, c, h).

Figure 2.

2-opt neighbourhood structure.

3-opt neighbourhood structure

The 3-opt neighbourhood structure cuts off three sub-paths and then makes all other possible forms of path restructuring connections. With eight measurement points, for example, four new restructuring paths will be obtained. As shown in Figure 3, the three sub-paths a-b, c-d and e-f in the initial path are selected to be cut off, and then all possible forms are exchanged to restructure the connections to obtain four new paths X1, X2, X3 and X4. The four candidate solutions are X1 = (a, e, d, b, c, f, g, h), X2 = (a, c, b, e, d, f, g, h), X3 = (a, d, e, c, b, f, g, h) and X4 = (a, d, e, b, c, f, g, h).

Figure 3.

3-opt neighbourhood structure.

Double-bridge neighbourhood structure

The double-bridge neighbourhood structure is a special constituent form of the 4-opt neighbourhood structure, where four sub-paths are cut off and then joined by a special path restructuring. As shown in Figure 4, the four sub-paths a-b, c-d, e-f and g-h in the initial path are selected and cut off. They are then restructured and connected in a way similar to two bridges to obtain a new path X1, and the candidate solution is X1 = (a, f, g, d, e, b, c, h).

Figure 4.

Double-bridge neighbourhood structure.

Parameter adaptive adjustment strategy

Based on the three neighbourhood structures mentioned in Section 3.2.1, the Levy flight is divided into three different distance steps, namely, long, medium and short distance steps, according to the degree of influence of the neighbourhood structure on the solution. Different neighbourhood structures are chosen for different distance steps of the Levy flight, and since the 2-opt neighbourhood structure has the least degree of influence on the solution, it is suitable for short distance steps to obtain candidate solutions. Conversely, the double-bridge neighbourhood structure, which has the greatest degree of influence on the solution, is suitable for obtaining candidate solutions at long distance steps. The 3-opt neighbourhood structure has a moderate degree of influence on the solution, so medium distance steps are applied to obtain candidate solutions. In addition, because the solutions obtained in the early host nest of the CS algorithm run are not optimal and there is a certain gap, it is necessary to choose long distance steps that have a greater influence on the solution so that the gap between the solution obtained in the early stage of the CS algorithm and the optimal solution is continuously reduced. As the CS algorithm continues to be updated iteratively, the solutions obtained later in the algorithm are high-quality solutions, at which point only minor adjustments to the solutions in the host nest are needed to obtain the optimal solution. Thus, the CS algorithm later on chooses short distance steps that have less impact on the solution. In summary, the step probability in this paper is a parameter that requires adaptive adjustment, and its value is dynamically adjusted with the number of iterations of the CS algorithm. The equations for the step probabilities are as follows:

\begin{matrix} P_{2 - opt} = 0.5 - 0.1 \times (\frac{1}{1 + e^{- \frac{N_{it} - 0.9 \times N_{max}}{10}}}) \\ - 0.2 \times (\frac{1}{1 + e^{- \frac{N_{it} - 0.5 \times N_{max}}{10}}}), \end{matrix}

(6)

P_{double - bridge} = 0.2 + 0.3 \times (\frac{1}{1 + e^{- \frac{N_{it} - 0.9 \times N_{max}}{10}}}),

(7)

P_{3 - opt} = 1 - P_{2 - opt} - P_{double - bridge},

(8)

where N_it and N_max represent the number of remaining iterations and the total number of iterations, respectively, P_2-opt represents the probability of a 2-opt neighbourhood structure, P_{double-bridge} represents the probability of a double-bridge neighbourhood structure, and P_3-opt represents the probability of a 3-opt neighbourhood structure.

2-opt optimisation strategy and initial probability dropout strategy

In the 2-opt optimisation strategy applied in the CS algorithm in this paper, all non-adjacent paths are connected by swapping them with each other. Then, the new path obtained by swapping is compared with the initial path, and the initial path is replaced with the new path if the length of the new path is smaller than the length of the initial path. Although the 2-opt optimisation strategy can improve the quality of the solution, it requires a lot of computing time. Therefore, the 2-opt optimisation strategy can be applied in the early stages of the CS algorithm to make significant improvements in the quality of the solution. However, in the later stages of the algorithm, the solutions obtained are of good quality and relatively stable, and applying a 2-opt optimisation strategy to each candidate solution set would consume a lot of computing time and would not necessarily result in a better solution. Therefore, this problem is solved by introducing a start-up probability dropout policy. The start-up probability dropout strategy is one that decreases the probability of applying the 2-opt optimisation strategy as the number of iterations of the algorithm increases.

The start-up probability P_dropout equation for the application of the 2-opt optimisation strategy is as follows:

P_{dropout} = 0.2 + 0.3 \times (\frac{1}{1 + e^{- \frac{N_{it} - 0.8 \times N_{max}}{10}}}),

(9)

where N_it and N_max represent the number of remaining iterations and the total number of iterations, respectively.

Dynamic neighbourhood structure

Since both the 2-opt neighbourhood structure and the 3-opt neighbourhood structure introduced in Section 3.2.1 obtain candidate solution sets by random edge selection, there will also be certain inferior candidate solution sets among them. In order to reduce the randomness of the CS algorithm, the ADNHCS algorithm in this paper will adopt a dynamic neighbourhood structure with round-limited mutation. With the 2-opt neighbourhood structure as an example, as shown in Figure 5, the lengths of the two edges in the original path are D1 and D2, and the corresponding lengths of the two edges after random restructuring are D3 and D4, respectively. It is evident in the figure that D1 + D2 < D3 + D4, so such restructuring is not only meaningless, but also increases the CS algorithm’s search time by a large amount and reduces the operational efficiency in the later iterations.

Figure 5.

2-opt random restructuring path length increase: (a) initial path and (b) stochastic restructuring path.

In summary, a dynamic neighbourhood structure is used in this paper in order to reduce the number of meaningless long distance path exchanges in the later stages of the CS algorithm. This dynamic neighbourhood structure allows the candidates for 2-opt and 3-opt neighbourhoods to be narrowed down to a near-neighbourhood range. First, a point in the set of measurement points is randomly selected, then the set of points within the nearest neighbourhood of the point is determined based on the radius R, defined as

\begin{matrix} R = {\begin{matrix} 2 \times \frac{L}{n}, 2 - opt \\ 3 \times \frac{L}{n}, 3 - opt \end{matrix}, \end{matrix}

(10)

The 2-opt neighbourhood structure is also used as an example, as shown in Figure 6. First, measurement point h is randomly selected as the centre of the circle, Figure 6(b), and the value of R is set according to equation (10). Then, the set of near-neighbourhood measurement points {a, b, c, d, f, g, h, i} of measurement point h was obtained. As shown in Figure 6(c), two sub-paths {c, d} and {h, i} in the near-neighbourhood measurement point set are randomly selected, cut off and restructured. Finally, a restructuring path is obtained, as shown in Figure 6(d).

Figure 6.

Neighbourhood selection and 2-opt restructuring: (a) initial path, (b) randomly select a measurement point, (c) select path and (d) restructure path.

Combination with taboo search algorithms

In order to extend the CS algorithm’s search in local neighbourhoods and improve the CS algorithm’s ability to jump out of local optimal solutions, this paper combines the CS algorithm with the forbidden search algorithm. The ADNHCS algorithm can select the most applicable solution of the current nest within the candidate solution set based on the taboo table and the aspiration criterion to obtain the global optimal solution more efficiently.

Based on the strategy in Section 3.2, the steps for implementing the ADNHCS algorithm are as follows:

Step 1: Set the algorithm parameters: population size pop, discovery probability Pa, maximum number of iterations N_max, and forbidden table length d.

Step 2: Randomly generate the initial solution set X = {X1, X2, …, Xpop} and calculate the fitness value f(Xi) for each individual in the initial solution set to obtain the current optimal solution X_best.

Step 3: Determine whether the set maximum number of iterations is reached, and if so, output the current optimal solution. If not, generate the candidate solution set S = {S1, S2, …, Sd} using Levy flight and the 2-opt optimisation strategy.

Step 4: Calculate the fitness value f(Si) for each individual in the candidate solution set S and use a forbidden search to check for superiority over the current solution and for a globally optimal solution.

Step 5: Generate a random number with r ∈ (0,1), and if r > Pa, a double-bridge shift needs to be applied to the optimal solution to generate a new solution in place of the current optimal solution.

Step 6: Determine if the set maximum number of iterations has been reached. If so, output the global optimal solution. If not, repeat Steps 3–5.

One specific implementation of the Levy flight in Step 3 to generate candidate solution sets is as follows:

Step 1: Generate a random number r ∈ (0,1) and determine that r lies in one of the probability intervals P_2-opt, P_3-opt and P_{double-bridge}.

Step 2: If the algorithm is in the first and middle iterations, the candidate solution set S = {S1, S2,…, Sd} is generated by applying the rules of different neighbourhood structures according to the located probability interval. If the algorithm is in the late iteration, the 2-opt neighbourhood structure and the 3-opt neighbourhood structure apply the rules of the dynamic neighbourhood structure to generate the candidate solution set S = {S1, S2,…, Sd}.

Step 3: Output the generated candidate solution set S.

Experiments and results

Simulation experiments

The intelligent algorithms studied in this paper were written and executed in MATLAB 2017a software. Computer system and configuration: Win10, CPU 2.60 GHz, 16 GB RAM. The ADNHCS algorithm parameters were set for the control group simulation experiments, and the final ADNHCS algorithm parameters were set as follows according to the test results: population size pop = 20, discovery probability Pa = 0.3, maximum number of iterations N_max = 100, and forbidden table length d = 20. In order to verify the advantages of the ADNHCS algorithm over other intelligent algorithms, it was compared with the genetic algorithm (GA), simulated annealing (SA) and ant colony optimisation (ACO) in simulation experiments. The research object of this study was an engine impeller model, and the set of sampling points on the impeller model was obtained by a random point distribution algorithm. The set of sampling points was divided into three groups of different sizes: 100, 200 and 400, distributed on one of the blades on the impeller model. The experimental objects as well as the distribution of the sampling set are shown in Figure 7. The results of each algorithm to optimise the paths of different-sized measurement points are shown in Figures 8 to 10.

Figure 7.

Impeller model and distribution of measurement points: (a) impeller model 100 measurement point distribution, (b) impeller model 200 measurement point distribution and (c) impeller model 400 measurement point distribution.

Figure 8.

Optimised 100-point path results for each algorithm.

Figure 9.

Optimised 200-point path results for each algorithm.

Figure 10.

Optimised 400-point path results for each algorithm.

The results of the ADNHCS algorithm and three conventional intelligent algorithms (SA, GA and ACO) for optimised the free-form surface inspection path are shown in Table 1. Among them, D_sa, D_ga, D_aco and D_adnhcs represent the length values of the SA, GA, ACO and ADNHCS optimised free-form surface inspection paths respectively. By analysing the results in Table 1, it can be concluded that the inspection paths optimised using the ADNHCS algorithm were at least 9.1%, 8.6% and 11.9% shorter than GA, SA and ACO, respectively. The ADNHCS algorithm optimised the 400 measurement point size, which was more than 24% shorter than the GA- and SA-optimised path lengths. Thus, the ADNHCS algorithm optimised better as the measurement point size increased.

Table 1.

Optimised path lengths for each algorithm.

Population size	100	200	400
D _sa (mm)	363	547	913
D _ga (mm)	361	566	930
D _aco (mm)	376	542	793
D _adnhcs (mm)	330	478	692
1 – D_adnhcs/D_sa	9.1%	12.7%	24.3%
1 – D_adnhcs/D_ga	8.6%	15.6%	25.6%
1 – D_adnhcs/D_aco	12.3%	11.9%	12.8%

The three traditional intelligent algorithms (SA, GA and ACO) and the ADNHCS algorithm run times are shown separately in Table 2, where T_sa represents the SA run time, T_ga represents the GA run time, T_aco represents the ACO run time and T_adnhcs represents the ADNHCS run time. Analysis of the experimental data in Table 2 shows that the run times using the ADNHCS algorithm were at least 67.7%, 35% and 68.3% shorter than those of the SA, GA and ACO, respectively, indicating that the ADNHCS algorithm had a large efficiency improvement over the three traditional intelligent algorithms for optimisation.

Table 2.

Run times for each algorithm.

Population size	100	200	400
T _sa (s)	213	298	588
T _ga (s)	42	78	292
T _aco (s)	46	143	598
T _adnhcs (s)	14	42	190
1 –T_adnhcs/T_sa	93.5%	86%	67.7%
1 –T_adnhcs/T_ga	66.7%	46.2%	35%
1 –T_adnhcs/T_aco	69.6%	70.7%	68.3%

In summary, the ADNHCS algorithm had a faster convergence speed and higher convergence accuracy relative to traditional intelligent algorithms, demonstrating the performance advantages of the ADNHCS algorithm.

Practical test experiments

The example impeller model inspection experiments in this paper were carried out on a Leitz Reference HP high precision coordinate measuring machine from Hexagon, Germany. Software to accompany the CMM: PC-DMIS software. The accuracy of the CMM: MPE_E = 0.9 +L/400 μm. The CMM probe size selection and parameter settings are as follows: the ball diameter is 5 mm, the probe movement speed is 20 mm/s, the touch and retreat speed of the probe is 2 mm/s, the positioning distance $d_{1}$ and retreat distance $d_{2}$ are both 2 mm. This CMM inspection of the measurement points on the impeller model used a point-to-point mode to ensure the accuracy of the inspection of the impeller model. The CMM was used to perform inspection sequences with the SA, GA, ACO and ADNHCS algorithms and to record the time taken for the entire inspection process for different size groups of measurement points. The PC-DMIS software simulation of the ADNHCS algorithm to optimise the path of the 400 measuring point probe movement is shown in Figure 11 and the CMM inspection of the impeller model is shown in Figure 12.

Figure 11.

Adaptive dynamic neighbourhood hybrid cuckoo search (ADNHCS)-algorithm-optimised path simulation in PC-DMIS software.

Figure 12.

Inspection of impeller part using CMM.

The results of the CMM inspection time for different size groups of measurement points are shown in Table 3, where t_sa represents the inspection path time after the SA algorithm has been optimised, t_ga represents the inspection path time after the GA algorithm has been optimised, t_aco represents the inspection path time after the ACO algorithm has been optimised and t_adnhcs represents the inspection path time after the ADNHCS algorithm has been optimised. From the inspection time results in Table 3, it can be seen that the path inspection efficiency optimised by the ADNHCS algorithm has been improved compared to several other intelligent algorithms, including at least 1.7% compared to SA inspection efficiency, at least 1.4% compared to GA inspection efficiency and at least 1.2% compared to ACO inspection efficiency. In addition, as the size of the measurement points increases, the efficiency of the ADNHCS algorithm improved significantly compared to SA and GA inspection.

Table 3.

Time consuming results of CMM inspection of different size groups of measurement points.

Population size	100	200	400
T _sa (s)	304	577	1138
t _ga (s)	303	580	1141
t _aco (s)	306	576	1122
t _adnhcs (s)	299	567	1109
1 –t_adnhcs/t_sa	1.7%	1.8%	2.6%
1 –t_adnhcs/t_ga	1.4%	2.3%	2.9%
1 –t_adnhcs/t_aco	2.3%	1.6%	1.2%

The advantages of the ADNHCS algorithm over the conventional intelligent algorithms to optimise free-form inspection paths were demonstrated through simulations and practical inspection tests. The performance advantages of the ADNHCS algorithm were mainly achieved through the extension of the neighbourhood structure of the CS algorithm and enrichment of the candidate solution set, thus improving the quality of the candidate solution set. At the same time, the global search capability of the algorithm was enhanced by implementing an adaptive adjustment strategy to the probability parameters for the different wandering distances of the Levy flight. The application of the starting probability dropout strategy to the 2-opt optimisation algorithm allowed the algorithm to converge quickly by avoiding invalid computations. In addition, by using a dynamic neighbourhood structure with round-limited mutations, it was possible to avoid invalid exchanges at long distances in the sub-paths, further improving the search efficiency of the algorithm.

Conclusions

In order to address the problems of long running time, long path length and low efficiency of traditional intelligent algorithms to optimise free-form surface inspection path algorithms, this paper proposed a method to optimise free-form surface inspection paths based on an improved cuckoo search algorithm. The proposed method improves the global search capability of the CS algorithm by introducing a parameter adaptive adjustment strategy and a dynamic neighbourhood search strategy on the basis of the CS algorithm. In addition, this paper also combines the CS algorithm with the forbidden search operator, which is able to make the CS algorithm jump out of the local optimum solution earlier. Thus, by improving the optimisation efficiency and optimisation accuracy of the CS algorithm, the length of the free-form surface inspection path and the inspection time are reduced. In order to verify the advantages and effectiveness of the ADNHCS algorithm to optimise free-form surface inspection paths, this paper compares the ADNHCS algorithm with three conventional intelligent algorithms (GA, SA and ACO) in simulations and example experiments respectively. The experimental results showed that the ADNHCS algorithm optimises free-form surfaces of different measurement point sizes, reducing the length of the inspection path by at least 9.1%, reducing the algorithm running time by at least 67.7% and improving the inspection efficiency by at least 1.7% compared to the SA. Compared to GA, the length of the inspection path is reduced by at least 8.6%, the algorithm running time is reduced by at least 35% and the inspection efficiency is improved by at least 1.4%. Compared to ACO, the length of the inspection path is reduced by at least 11.9%, the algorithm run time is reduced by at least 68.3% and the inspection efficiency is improved by at least 1.2%. Based on simulation results and actual inspection results, it can be seen that the ADNHCS algorithm could shorten the optimisation time and inspection path length of the free-form surface inspection path compared to those of the traditional intelligent algorithm, resulting in an increase in the inspection efficiency and a reduction in manufacturing costs.

This paper focused on the application of a new intelligent algorithm versus traditional intelligent algorithms to optimise free-form surface inspection paths. Various methods to improve the detection efficiency, such as picking strategies, automatic collision inspection algorithms, and algorithms to minimise the number of probe changes of direction, could be the subject of subsequent research. In addition, in-depth research of new and traditional intelligent algorithms can continue, further improving the performance of the algorithm and enabling further improvements in the inspection efficiency.

Footnotes

Acknowledgements

We thank LetPub () for its linguistic assistance during the preparation of this manuscript.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was financially supported by the National Nature Science Foundation of China (51565006, 52165054), the Natural Science Foundation of Guangxi Province (2018GXNSFAA050085, 2020GXNSFAA1591), the Science Research Innovation Team Project of Guangxi Provincial Education Department, and the Science Research Innovation Team Project of Guangxi University of Science and Technology.

ORCID iDs

Yueping Chen

Bo Tan

References

Zahmati

Amirabadi

Mehrad

. A hybrid measurement sampling method for accurate inspection of geometric errors on freeform surfaces. Measurement 2018; 122: 155–167.

Aliakbari

Mahboubkhah

. An adaptive computer-aided path planning to eliminate errors of contact probes on free-form surfaces using a 4-DOF parallel robot CMM and a turn-table. Measurement 2020; 166: 108216.

Huang

, et al. CAD-based measurement planning strategy of complex surface for five axes on machine verification. Int J Adv Manuf Technol 2017; 91: 2101–2111.

Liu

Zhao

Sun

, et al. Optimal path planning for automated dimensional inspection of free-form surfaces. J Manuf Syst 2020; 56: 84–92.

Qiao

Hua

, et al. Touch Trigger probe-based interference-free inspection path planning for free-form surfaces by optimizing the probe posture. IEEE Trans Instrum Meas 2022; 71: 1–8.

Zeng

Tang

, et al. Orientation-point relation based inspection path planning method for 5-axis OMI system. Robot Comput Integr Manuf 2020; 61: 101827.

Mian

Al-Ahmari

. Enhance performance of inspection process on coordinate measuring machine. Measurement 2014; 47: 78–91.

Chen

Shang

. Comparison of GA, ACO algorithm, and PSO algorithm for path optimization on free-form surfaces using coordinate measuring machines. Eng Res Exp 2021; 3: 045039.

Stojadinovic

Majstorovic

Durakbasa

, et al. Ants colony optimisation of a measuring path of prismatic parts on a CMM. Metrol Measurement Syst 2016; 23: 119–132.

10.

Liu

Adayi

Wang

. An improved genetic algorithm for measuring path optimization of spiral bevel gear tooth surface. Mech Sci Technol Aerosp Eng 2022; 41: 445–450.

11.

Di Placido

Archetti

Cerrone

. A genetic algorithm for the close-enough traveling salesman problem with application to solar panels diagnostic reconnaissance. Comput Oper Res 2022; 145: 105831.

12.

Abhishek

Ranjit

Shankar

, et al. Hybrid PSO-HSA and PSO-GA algorithm for 3D path planning in autonomous UAVs. SN Appl Sci 2020; 2: 1805.

13.

Puspita

Meitrilova

Yahdin

. Mathematical modelling of traveling salesman problem (TSP) by implementing simulated annealing and genetic algorithms. J Phys Conf Ser 2020; 1480: 012029.

14.

Chen

Tan

. Free-form surface inspection path planning using improved ant colony optimisation algorithm. Eng Res Exp 2022; 4: 035039.

15.

Yang

Wang

Zhang

. Parameter Analysis and simulation experiment of ant colony optimization on small-scale TSP problem. IOP Conf Ser Mater Sci Eng 2020; 768: 072095.

16.

Osaba

Yang

X-S

Diaz

, et al. An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems. Eng Appl Artif Intell 2016; 48: 59–71.

17.

Saji

Riffi

. A novel discrete bat algorithm for solving the travelling salesman problem. Neural Comput Appl 2016; 27: 1853–1866.

18.

Ardalan

Karimi

Poursabzi

, et al. A novel imperialist competitive algorithm for generalized traveling salesman problems. Appl Soft Comput 2015; 26: 546–555.

19.

Panwar

Deep

. Discrete Grey Wolf Optimizer for symmetric travelling salesman problem. Appl Soft Comput 2021; 105: 107298.

20.

Ouaarab

Ahiod

Yang

X-S

. Discrete cuckoo search algorithm for the travelling salesman problem. Neural Comput Appl 2014; 24: 1659–1669.

21.

Ouaarab

Ahiod

Yang

X-S

. Random-key cuckoo search for the travelling salesman problem. Soft Comput 2015; 19: 1099–1106.

22.

Yang

X-S

Deb

. Cuckoo search via Lévy flights. In: World congress on nature and biologically inspired computing, 2009, pp.210–214. New York: IEEE.

Inspection path planning of free-form surfaces based on improved cuckoo search algorithm

Abstract

Keywords

Introduction

Mathematical model for inspection paths

Inspection path optimisation using improved cuckoo search algorithm

Cuckoo search algorithm

Improved cuckoo search algorithm

Neighbourhood structure

2-opt neighbourhood structure

3-opt neighbourhood structure

Double-bridge neighbourhood structure

Parameter adaptive adjustment strategy

2-opt optimisation strategy and initial probability dropout strategy

Dynamic neighbourhood structure

Combination with taboo search algorithms

Experiments and results

Simulation experiments

Practical test experiments

Conclusions

Footnotes

Acknowledgements

Declaration of conflicting interests

Funding

ORCID iDs

References