爬山算法 - 数学建模社区-数学中国

假设我们需要找到函数 𝑓(𝑥)=−𝑥^2+4𝑥的最大值。这是一个具有单个局部最大值的简单抛物线函数。

首先，定义我们需要优化的函数。在MATLAB中，我们可以创建一个函数来计算给定x值的 𝑓(𝑥)。

复制代码

接着，实现爬山算法。我们从一个随机点开始，然后在每一步尝试移动到一个“邻居”点，如果那里的值更高，就移动到那里。

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations)
# D, `- M- C& i% W* S
currentX = initialX;
# Q/ ^' \1 Q w0 L+ [& e2 i/ o
currentY = func(currentX);
6 B. X' {* }) H& E) c: P1 B6 u
for i = 1:numIterations7 P- J! t6 l$ G
% 尝试在两个方向上移动
0 `' {- V8 N0 W' u9 d( U( h% J- ^
newX = [currentX + stepSize, currentX - stepSize];
# S8 m3 w1 c$ J+ y1 ], j# y7 R6 C
newY = [func(newX(1)), func(newX(2))];
6 B; b9 a1 _4 H7 Z
: \ M2 L( ~% P* ?. M
% 找出最好的移动方向) o( B3 @; z: q8 Q$ ~; R
[maxY, idx] = max(newY);+ _2 v4 O7 a& G
: C- L; L( ^/ `6 M1 G, S
% 如果找到了更好的解，则更新当前解
' k) M' D/ Y5 u) D; d
if maxY > currentY
2 ?/ f. S& H0 n# s9 p- G6 D( o
currentX = newX(idx);0 A: I, T8 e. J: ~
currentY = maxY;. b$ D+ p+ E* Z: n; Z- ^, n
else8 r; u5 J6 K1 s, X* v
% 如果没有更好的解，结束搜索
" ]! u) I, ` e" S
break;4 D4 O) Q$ V' @8 X
end1 J2 ^; m0 m5 ~' v+ I" E6 [- o
end* M I {. I" D V
bestX = currentX;$ z, L; q8 N( k; P9 O$ |
bestY = currentY;3 G* g' x0 z4 F- Y0 k
end% x a3 \! p8 _3 m; o. D
5 ~' J- m9 }6 b2 o: d* D/ @% Q2 y& g3 m
% 运行爬山算法
9 H* k2 n6 |8 c5 [( {/ a
initialX = 0; % 初始点$ `5 U; F9 ~5 t0 h8 g7 \3 A
stepSize = 0.1; % 步长# J r6 H# B/ ^& Q8 V! a
numIterations = 100; % 迭代次数
9 X+ {, U. T1 U- [3 o; C
[bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

复制代码

disp(['The maximum value of f(x) is found at x = ', num2str(bestX)]);
; i- p# [7 R! z, r9 t/ }
disp(['The maximum value of f(x) is ', num2str(bestY)]);

复制代码

可视化函数和算法找到的最大值点，以更好地理解算法的行为。

x = 0:0.01:5;1 r5 Y s& C' s1 O1 B
y = myFunction(x);
; L/ T0 E9 I8 }, W9 E% k
figure;- i# `1 Q& t( w% G& n( C
plot(x, y, 'b-', bestX, bestY, 'ro');
7 }( w" e$ V5 _ L& s. M8 N: b. O
title('Function Optimization using Hill Climbing');$ h: u* x# s, [$ s' e' }8 E) Y
xlabel('x');
# v. k L, W8 Q; Z
ylabel('f(x)');
% ^3 A3 a. r* K/ C) c7 N
legend('Function', 'Maximum Point');

复制代码