模拟退火算法解决旅行商问题（TSP）

野性酷女 2022-08-30 00:49 229阅读 0赞

本文是使用Matlab实现模拟退火算法解决旅行商问题（TSP）

模拟退火是模仿冶金中退火过程的爬山法的改进版本。

### 模拟退火 ###

模拟退火是一种用于解决无约束优化问题的优化算法。该方法模拟加热材料然后缓慢降低温度以减少缺陷的物理过程，从而最大限度地减少系统能量。

本地搜索

局部搜索是一种用于解决计算困难的优化问题的启发式方法。局部搜索可用于解决问题，这些问题可以表述为在多个候选解决方案中找到最大化标准的解决方案。局部搜索算法通过应用局部变化在候选解决方案空间（搜索空间）中从一个解决方案移动到另一个解决方案，直到找到被认为是最佳的解决方案或经过了时间限制。

代码：

clear all
    close all
    clc
    
    %% Problem preparation 
    
    % Create the graph 
    graphNo = 1; 
    [ graph ]  = createGraph(2);
    nVar = graph.n;
    
    A.position = randperm(nVar);
    A.cost = fitnessFunction ( [A.position,  A.position(1)]  , graph);
    
    
    % Draw the graph 
    figure 
    set(gcf,'position' , [50,50,700,700])
    subplot(2,2,1)
    drawGraph( graph); 
    
    
    %% SA algorithm 
    
    %% Initial parameters of ACO 
    T0=1;       % Initial Temp.
    T=T0;
    
    alphaa=0.99;     % Cooling factor
    maxIteration = 500;
    
    
    %% Main loop of SA 
    
    bestFitness = inf;
    bestTour = [];
    fitness_hist = 0;
    
    for t = 1 : maxIteration
        
        fitness_hist(t) = A.cost;
        
        B.position=createNeighbour(A.position);
        B.cost = fitnessFunction ( [B.position,  B.position(1)] , graph);
        
        Delta = A.cost - B.cost;
    
        if Delta < 0  % uphill move (good move)
            A.cost = B.cost;
            A.position = B.position;
        else % downhill move (bad move)
            P=exp(-Delta/T);
            if rand<=P
                A.cost = B.cost;
                A.position = B.position;
            end
        end
    
        
        % Update Temp.
        T=alphaa*T;
        
        % Display the results 
        
        outmsg = [ 'Iteration #' , num2str(t) , ' Shortest length = ' , num2str(A.cost)  ];
        disp(outmsg)
        subplot(2,2,2)
        title(['Iteration #' , num2str(t) ])
        % Visualize best tour and phromone concentration
        cla
        drawBestTour( A.position, graph );
        
        
        subplot(2,2,[3 4]);
        plot(fitness_hist)
        xlabel('Iteration')
        ylabel('-Best tour length')
        
       drawnow
    end

运行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3VwZGF0ZTc_size_16_color_FFFFFF_t_70][]

获取完整代码：[https://ai.52learn.online/code/42][https_ai.52learn.online_code_42]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3VwZGF0ZTc_size_16_color_FFFFFF_t_70]: /images/20220829/094363572dc34caa98ecf25f91cd61ee.png
[https_ai.52learn.online_code_42]: https://ai.52learn.online/code/42