一、TSP簡介
旅行商問題，即TSP問題（Traveling Salesman Problem）又譯為旅行推銷員問題、貨郎擔問題，是數學領域中著名問題之一。假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市隻能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目标是要求得的路徑路程為所有路徑之中的最小值。
TSP的數學模型
二、遺傳算法簡介
1 引言
2 遺傳算法理論
2.1 遺傳算法的生物學基礎
2.2 遺傳算法的理論基礎
2.3 遺傳算法的基本概念
2.4 标準的遺傳算法
2.5 遺傳算法的特點
2.6 遺傳算法的改進方向
3 遺傳算法流程
4 關鍵參數說明
三、部分源代碼
function varargout = gaGui(varargin)
% GAGUI M-file for gaGui.fig
% GAGUI, by itself, creates a new GAGUI or raises the existing
% singleton*.
%
% H = GAGUI returns the handle to a new GAGUI or the handle to
% the existing singleton*.
%
% GAGUI('CALLBACK',hObject,eventData,handles,...) calls the local
% function named CALLBACK in GAGUI.M with the given input arguments.
%
% GAGUI('Property','Value',...) creates a new GAGUI or raises the
% existing singleton*. Starting from the left, property value pairs are
% applied to the GUI before gaGui_OpeningFunction gets called. An
% unrecognized property name or invalid value makes property application
% stop. All inputs are passed to gaGui_OpeningFcn via varargin.
%
% *See GUI Options on GUIDE's Tools menu. Choose "GUI allows only one
% instance to run (singleton)".
%
% See also: GUIDE, GUIDATA, GUIHANDLES
% Begin initialization code - DO NOT EDIT
gui_Singleton = 1;
gui_State = struct('gui_Name', mfilename, ...
'gui_Singleton', gui_Singleton, ...
'gui_OpeningFcn', @gaGui_OpeningFcn, ...
'gui_OutputFcn', @gaGui_OutputFcn, ...
'gui_LayoutFcn', [] , ...
'gui_Callback', []);
if nargin && ischar(varargin{1})
gui_State.gui_Callback = str2func(varargin{1});
end
if nargout
[varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:});
else
gui_mainfcn(gui_State, varargin{:});
end
% End initialization code - DO NOT EDIT
% --- Executes just before gaGui is made visible.
function gaGui_OpeningFcn(hObject, eventdata, handles, varargin)
% This function has no output args, see OutputFcn.
% hObject handle to figure
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% varargin command line arguments to gaGui (see VARARGIN)
% Choose default command line output for gaGui
handles.output = hObject;
% Update handles structure
guidata(hObject, handles);
% UIWAIT makes gaGui wait for user response (see UIRESUME)
% uiwait(handles.figure1);
% --- Outputs from this function are returned to the command line.
function varargout = gaGui_OutputFcn(hObject, eventdata, handles)
% varargout cell array for returning output args (see VARARGOUT);
% hObject handle to figure
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Get default command line output from handles structure
varargout{1} = handles.output;
function EditCityNumber_Callback(hObject, eventdata, handles)
% hObject handle to EditCityNumber (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of EditCityNumber as text
% str2double(get(hObject,'String')) returns contents of EditCityNumber as a double
% --- Executes during object creation, after setting all properties.
function EditCityNumber_CreateFcn(hObject, eventdata, handles)
% hObject handle to EditCityNumber (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
function edit3_Callback(hObject, eventdata, handles)
% hObject handle to edit3 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit3 as text
% str2double(get(hObject,'String')) returns contents of edit3 as a double
% --- Executes during object creation, after setting all properties.
function edit3_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit3 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
function editInitialGroup_Callback(hObject, eventdata, handles)
% hObject handle to editInitialGroup (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of editInitialGroup as text
% str2double(get(hObject,'String')) returns contents of editInitialGroup as a double
% --- Executes during object creation, after setting all properties.
function editInitialGroup_CreateFcn(hObject, eventdata, handles)
% hObject handle to editInitialGroup (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
function EditCrossOver_Callback(hObject, eventdata, handles)
% hObject handle to EditCrossOver (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of EditCrossOver as text
% str2double(get(hObject,'String')) returns contents of EditCrossOver as a double
% --- Executes during object creation, after setting all properties.
function EditCrossOver_CreateFcn(hObject, eventdata, handles)
% hObject handle to EditCrossOver (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
function edit6_Callback(hObject, eventdata, handles)
% hObject handle to edit6 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit6 as text
% str2double(get(hObject,'String')) returns contents of edit6 as a double
% --- Executes during object creation, after setting all properties.
function edit6_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit6 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor','white');
end
% --- Executes on button press in GenerateInitialCitiesButton.
function GenerateInitialCitiesButton_Callback(hObject, eventdata, handles)
% hObject handle to GenerateInitialCitiesButton (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
str1=char(get(handles.EditCityNumber,'string'));
global N
N=str2num(str1);
%生成随即城市
global cities;
if(~isempty(cities))
cla;
end
cities=round(100*rand(N,2));
axes(handles.CityMap);
for k=1:N
if(k~=1)
hold on
end
plot(cities(k,1),cities(k,2),'bo');
end
四、運作結果
五、matlab版本及參考文獻
1 matlab版本
2014a
2 參考文獻
[1] 包子陽,餘繼周,楊杉.智能優化算法及其MATLAB執行個體（第2版）[M].電子工業出版社，2016.
[2]張岩,吳水根.MATLAB優化算法源代碼[M].清華大學出版社，2017.