查看: 2467|回复: 0

爬山算法

字体大小: 正常放大

1186 主题	4 听众	2922 积分

该用户从未签到

电梯直达

1^#

发表于 2024-4-26 15:44 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

使用爬山算法优化简单的数学函数

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

步骤 1: 定义目标函数

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

function y = myFunction(x)
; e4 O. T+ o& H$ V& e
y = -x^2 + 4*x;/ I7 q6 g: R2 E$ e& T: o% R; \
end

步骤 2: 实现爬山算法

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

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations)0 E. j% k5 T# F4 [! N
currentX = initialX;# X8 m- a, X- ]: [' l+ h$ a& \
currentY = func(currentX);8 a. {- r1 J( B: s d; E5 B7 b
for i = 1:numIterations
) j' F+ Q( T- g
% 尝试在两个方向上移动
/ u& i0 v/ i, c+ w& M/ N/ n( P
newX = [currentX + stepSize, currentX - stepSize];. `; W2 S3 w( H* Q! j+ C- v
newY = [func(newX(1)), func(newX(2))];; f! s0 o2 ~2 q0 P2 S
8 w, \0 _7 \3 O; k8 H( a
% 找出最好的移动方向
\\" M. F$ X$ ~! C( Q( C3 P\\" g; V
[maxY, idx] = max(newY);+ |# z$ j1 f$ l. U
; _& v! Y2 n) }\\" N. B* b
% 如果找到了更好的解，则更新当前解# u/ b ?5 E: T
if maxY > currentY
; A; X. y9 F: ^$ |
currentX = newX(idx);
3 ~+ j7 G5 C2 x9 H' J1 o
currentY = maxY;
* S1 [* r1 u. u\\" I
else' y6 ~$ u+ M, i) D; m4 {
% 如果没有更好的解，结束搜索* d6 G- v6 t) U7 D. n, v: S
break;! r$ B% p0 I$ A3 C1 P. Q6 c7 e4 ~7 u
end+ v& ` P6 A) n4 N. c1 Z
end
7 N( K2 o% {) m/ }& I
bestX = currentX;
# s\\" ^; u. f# b4 n) U x3 H, Y9 B
bestY = currentY;
2 }. v% S/ N2 ~3 ]3 R
end\\" q K% R( N. j: q( r\\" o8 o
$ f6 e2 [9 `* q\\" g2 |
% 运行爬山算法) g$ d. B5 s* J R& x! t# l
initialX = 0; % 初始点
|$ P) z4 L# t. I- \
stepSize = 0.1; % 步长
- s8 _1 W, M( c: R( t+ w
numIterations = 100; % 迭代次数. I0 m: t) z# j6 l: u( P) }
[bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations)0 E. j% k5 T# F4 [! N

currentX = initialX;# X8 m- a, X- ]: [' l+ h$ a& \

currentY = func(currentX);8 a. {- r1 J( B: s  d; E5 B7 b

for i = 1:numIterations 
) j' F+ Q( T- g
        % 尝试在两个方向上移动 
/ u& i0 v/ i, c+ w& M/ N/ n( P
        newX = [currentX + stepSize, currentX - stepSize];. `; W2 S3 w( H* Q! j+ C- v

newY = [func(newX(1)), func(newX(2))];; f! s0 o2 ~2 q0 P2 S

8 w, \0 _7 \3 O; k8 H( a

% 找出最好的移动方向 
\\" M. F$ X$ ~! C( Q( C3 P\\" g; V
        [maxY, idx] = max(newY);+ |# z$ j1 f$ l. U

; _& v! Y2 n) }\\" N. B* b

% 如果找到了更好的解，则更新当前解# u/ b  ?5 E: T

if maxY > currentY 
; A; X. y9 F: ^$ |
            currentX = newX(idx); 
3 ~+ j7 G5 C2 x9 H' J1 o
            currentY = maxY; 
* S1 [* r1 u. u\\" I
        else' y6 ~$ u+ M, i) D; m4 {

% 如果没有更好的解，结束搜索* d6 G- v6 t) U7 D. n, v: S

break;! r$ B% p0 I$ A3 C1 P. Q6 c7 e4 ~7 u

end+ v& `  P6 A) n4 N. c1 Z

end 
7 N( K2 o% {) m/ }& I
    bestX = currentX; 
# s\\" ^; u. f# b4 n) U  x3 H, Y9 B
    bestY = currentY; 
2 }. v% S/ N2 ~3 ]3 R
end\\" q  K% R( N. j: q( r\\" o8 o

$ f6 e2 [9 `* q\\" g2 |
% 运行爬山算法) g$ d. B5 s* J  R& x! t# l

initialX = 0; % 初始点 
  |$ P) z4 L# t. I- \
stepSize = 0.1; % 步长 
- s8 _1 W, M( c: R( t+ w
numIterations = 100; % 迭代次数. I0 m: t) z# j6 l: u( P) }

[bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

步骤 3: 输出结果

展示算法找到的最优解。

disp(['The maximum value of f(x) is found at x = ', num2str(bestX)]);- {: ` h9 N/ A2 S: O# X( P2 I( z7 m
disp(['The maximum value of f(x) is ', num2str(bestY)]);

复制代码

步骤 4: 可视化

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

x = 0:0.01:5;% h* t6 c2 d' X! H- C
y = myFunction(x);! {+ X# v/ R3 d% Z6 i; r
figure;& r3 M3 A$ i$ O4 K) @& E- L
plot(x, y, 'b-', bestX, bestY, 'ro');
* Q- S4 Z: v4 j1 Y7 k
title('Function Optimization using Hill Climbing');# v\\" O1 o) M% z0 _/ w0 x! _# l4 v3 v' q
xlabel('x');
, v# Z. g u1 {\\" f7 m\\" n& [) N
ylabel('f(x)');
/ f; n+ C2 s4 V
legend('Function', 'Maximum Point');