Make writing a habit together! This is the fourth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.
1 tabu Search algorithm (generalized neighborhood search algorithm)
1.1 Core Ideas:
Generates a current solution, generates its neighborhood solution in a certain way, and the neighborhood solution forms a set, called the candidate solution set. Then, the best solution is selected from the candidate solution set and compared with the current solution.
1.2 Amnesty Criteria
Consider whether the solution meets the amnesty criteria: that is, the solution is not limited by its taboo length, as long as it meets the amnesty criteria can be released from the taboo list. Continue to participate in normal update iterations.
1.3 Taboos:
You can taboo the complete solution, you can also taboo partial vectors of the solution, and you can also taboo all solutions corresponding to a certain target value.
2 simulated annealing algorithm
2.1 Core Ideas:
Generate a new state from the current state, and then compare the current state with the new state. If the new state is better than the current state: replace it. If the new state is worse than the current state: replace with a certain probability.
2.2 Design of the cycle
Internal loop: Sampling many times at one temperature. External circulation: sampling at different temperatures.
3 Genetic Algorithm
Search in parallel in the form of population.
3.1 Important Operations:
Based on the problem, the problem space is converted to the algorithm space (coding work) Problem evaluation and adaptation calculation (decoding)
3.2 Coding principles:
- Each of these chromosomes represents a viable solution to the solution space.
- The chromosomes encoded according to the coding rules can represent all the solutions of the solution space.
Ant colony algorithm
Construct a path for the ant during the process of the algorithm (that is, the solution is constructed during the process of the algorithm), instead of directly generating the initial solution as before. After constructing each path, update the pheromone quantity of each path.
Construction elements of generalized neighborhood search algorithm
- Search mechanism selection: search framework; Different algorithms do different things in each iteration
- Search method selection: a single individual to search; Group search
- Neighborhood function design: Generate new states
- Design of status update mode: update formula
- Selection of modification criteria and methods for control parameters: adaptive parameter setting
- Design of Termination Criteria for Algorithms: When to Stop? Number of iterations; The number of generations does not change; Enter the precision range;
6. Optimize the performance evaluation index of the algorithm
- Optimization index: good, can find the optimal solution, each time calculated out of the solution distance problem optimal solution is how close
- Time performance indicator: Fast
- Robustness index: stable, whether the results of each operation are good (robustness index is commonly used in dynamic problems)