Skip to content
TheChatArchiveThe Chat Archive
gpt-4-0314· openaiHugging Face Suzhen/CodeChat

以下是一个简单的萤火虫算法的MATLAB代码,用于解决TSPD问题。

  1. User

    以下是一个简单的萤火虫算法的MATLAB代码,用于解决TSPD问题。

  2. Assistant

    function [best_cost, best_path, best_grocery] = firefly_TSPD(distance_matrix, attraction_matrix)

    %% Parameters n = 50; % number of fireflies alpha = 0.2; % randomization parameter beta0 = 1; % attractiveness at r = 0 gamma = 1; % light absorption coefficient max_gen = 100; % maximum number of iterations n_stall = 10; % number of iterations with no improvement before stopping

    %% Initialize fireflies fireflies = cell(1, n);

    for i = 1:n fireflies{i}.path = randperm(size(distance_matrix, 1)); % random permutation of cities fireflies{i}.grocery = randi([0, 1], size(distance_matrix, 1), 1); % random grocery selection fireflies{i}.cost = calculate_cost(fireflies{i}.path, fireflies{i}.grocery, distance_matrix, attraction_matrix); end

    %% Firefly algorithm best_cost = inf; best_path = []; best_grocery = []; stall_count = 0;

    for gen = 1:max_gen % Update fireflies for i = 1:n for j = 1:n if fireflies{j}.cost < fireflies{i}.cost r = calculate_distance(fireflies{i}.path, fireflies{j}.path, distance_matrix); beta = beta0 * exp(-gamma * r^2); new_path = update_path(fireflies{i}.path, fireflies{j}.path, alpha, beta); new_grocery = update_grocery(fireflies{i}.grocery, fireflies{j}.grocery, alpha, beta); new_cost = calculate_cost(new_path, new_grocery, distance_matrix, attraction_matrix);

                if new_cost < fireflies{i}.cost
                    fireflies{i}.path = new_path;
                    fireflies{i}.grocery = new_grocery;
                    fireflies{i}.cost = new_cost;
                end
            end
        end
    end
    
    % Find best solution
    [~, best_idx] = min([fireflies{:}.cost]);
    current_best_cost = fireflies{best_idx}.cost;
    
    if current_best_cost < best_cost
        best_cost = current_best_cost;
        best_path = fireflies{best_idx}.path;
        best_grocery = fireflies{best_idx}.grocery;
        stall_count = 0;
    else
        stall_count = stall_count + 1;
    end
    
    % Check stopping condition
    if stall_count >= n_stall
        break;
    end
    

    end

    end

    function cost = calculate_cost(path, grocery, distance_matrix, attraction_matrix) cost = sum(distance_matrix(sub2ind(size(distance_matrix), path, [path(2:end), path(1)]))) + ... sum(attraction_matrix(:, 1)' .* ~grocery' .* path) + ... sum(attraction_matrix(:, 2)' .* grocery' .* (1 - path)); end

    function r = calculate_distance(path1, path2, distance_matrix) r = sum(diag(distance_matrix(path1, path2))); end

    function new_path = update_path(path1, path2, alpha, beta) % This is a rough example, you may want to implement a more sophisticated path update mechanism new_path = path1;

    for i = 1:length(path1)
        if rand < beta
            idx = find(path2 == path1(i));
            new_path([i, idx]) = new_path([idx, i]);
        end
    end
    

    end

    function new_grocery = update_grocery(grocery1, grocery2, alpha, beta) new_grocery = grocery1;

     for i = 1:length(grocery1)
         if rand < beta
             new_grocery(i) = grocery2(i);
         elseif rand < alpha
             new_grocery(i) = ~new_grocery(i);
         end
     end
    

    end

  3. User

    请给出求解TSPD问题的GSO算法的MATLAB代码,并给出求解实例

  4. Assistant

    在下面的示例代码中,我们使用了Glowworm Swarm Optimization(GSO)算法来解决TSPD问题。代码首先定义了一些辅助函数,然后是主要的GSO算法。最后,代码给出了一个用于测试的TSPD实例。

    function [best_cost, best_path, best_grocery] = gso_TSPD(distance_matrix, attraction_matrix)
    
    %% Parameters
    n = 50; % number of glowworms
    nt = 0.1; %neighborhood threshold
    max_gen = 100; % maximum number of iterations
    l0 = 5; % initial luciferin
    beta = 0.1; % luciferin decay constant
    gamma = 0.2; % luciferin enhancement constant
    step_size = 1.0; %Step size
    
    %% Initialize glowworms
    glowworms = cell(1, n);
    
    for i = 1:n
        glowworms{i}.path = randperm(size(distance_matrix, 1)); % random permutation of cities
        glowworms{i}.grocery = randi([0, 1], size(distance_matrix, 1), 1); % random grocery selection
        glowworms{i}.cost = calculate_cost(glowworms{i}.path, glowworms{i}.grocery, distance_matrix, attraction_matrix);
        glowworms{i}.luciferin = l0;
    end
    
    %% GSO algorithm
    best_cost = inf;
    best_path = [];
    best_grocery = [];
    
    for gen = 1:max_gen
        % Update luciferin
        for i = 1:n
            glowworms{i}.luciferin = (1 - beta) * glowworms{i}.luciferin + gamma * (1 / glowworms{i}.cost);
        end
        
        % Nearest neighbor step
        for i = 1:n
            neighbors = find_neighbors(glowworms, i, distance_matrix, nt);
            [~, max_idx] = max([neighbors{1,:}.luciferin]);
            chosen_glowworm = neighbors{1, max_idx};
            new_path = local_search(glowworms{i}.path, chosen_glowworm.path, step_size);
            new_grocery = update_grocery(glowworms{i}.grocery, chosen_glowworm.grocery);
            new_cost = calculate_cost(new_path, new_grocery, distance_matrix, attraction_matrix);
    
            if new_cost < glowworms{i}.cost
                glowworms{i}.path = new_path;
                glowworms{i}.grocery = new_grocery;
                glowworms{i}.cost = new_cost;
            end
        end
    
        % Update the best solution
        [~, best_idx] = min([glowworms{:}.cost]);
        current_best_cost = glowworms{best_idx}.cost;
    
        if current_best_cost < best_cost
            best_cost = current_best_cost;
            best_path = glowworms{best_idx}.path;
            best_grocery = glowworms{best_idx}.grocery;
        end
    
    end
    
    end
    
    function neighbors = find_neighbors(glowworms, idx, distance_matrix, nt)
        distances = zeros(1, numel(glowworms));
    
        for j = 1:numel(glowworms)
            distances(j) = calculate_distance(glowworms{idx}.path, glowworms{j}.path, distance_matrix);
        end
    
        neighbors_idx = find(distances <= nt);
        neighbors = glowworms(neighbors_idx);
    end
    
    function cost = calculate_cost(path, grocery, distance_matrix, attraction_matrix)
        cost = sum(distance_matrix(sub2ind(size(distance_matrix), path, [path(2:end), path(1)]))) + ...
               sum(attraction_matrix(:, 1)' .* ~grocery' .* path) + ...
               sum(attraction_matrix(:, 2)' .* grocery' .* (1 - path));
    end
    
    function r = calculate_distance(path1, path2, distance_matrix)
        r = sum(diag(distance_matrix(path1, path2)));
    end
    
    function new_path = local_search(current_path, chosen_path, step_size)
        % Simple local search
        new_path = current_path;
        for i = 1:step_size
            c1 = randi(length(new_path), 1);
            c2 = randi(length(chosen_path), 1);
            [~, p1] = ismember(current_path(c1), chosen_path);
            [~, p2] = ismember(chosen_path(c2), current_path);
            new_path([p1, p2]) = new_path([p2, p1]);
        end
    end
    
    function new_grocery = update_grocery(grocery1, grocery2)
         new_grocery = grocery1;
    
         for i = 1:length(grocery1)
             if rand < 0.5
                 new_grocery(i) = grocery2(i);
             end
         end
    end
    
    %% Solving the TSPD instance
    distance_matrix = [0, 5, 7, 3, 11; 5, 0, 6, 4, 8; 7, 6, 0, 2, 3; 3, 4, 2, 0, 6; 11, 8, 3, 6, 0];
    attraction_matrix = [8, 9; 7, 10; 12, 6; 11, 13; 5, 7];
    
    [best_cost, best_path, best_grocery] = gso_TSPD(distance_matrix, attraction_matrix);
    
    disp('Best cost:')
    disp(best_cost)
    disp('Best path:')
    disp(best_path)
    disp('Best grocery:')
    disp(best_grocery)
    

    上述代码使用一个简单的TSPD实例进行测试,有5个城市,距离矩阵存储在distance_matrix中,吸引力矩阵存储在attraction_matrix中。运行GSO算法后,将打印出最佳成本、最佳路径和最佳杂货选择。

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.