数学建模社区-数学中国

标题: 爬山算法 [打印本页]
作者: 2744557306    时间: 2024-4-26 15:44
标题: 爬山算法
使用爬山算法优化简单的数学函数

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


. Z" o" U, J- H8 Y: U! J! V. I- d& X步骤 1: 定义目标函数

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

  1. function y = myFunction(x)
    , U1 t$ n6 @# J  F
  2.     y = -x^2 + 4*x;
    6 ]# d- r% c* U/ E6 s' T7 Q2 v: O
  3. end
复制代码
步骤 2: 实现爬山算法

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

  1. function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations): j& J1 a& D4 R1 Z0 }/ x* V
  2.     currentX = initialX;/ Q9 i6 x  t! q% b7 s( j$ z
  3.     currentY = func(currentX);
    : |& |0 X! @7 {% q% T  d
  4.     for i = 1:numIterations( w0 _3 U4 V! Q5 T% _, a) p
  5.         % 尝试在两个方向上移动3 M) ~8 ~- @0 V/ c
  6.         newX = [currentX + stepSize, currentX - stepSize];6 C- h1 J" L# ?. W# c- M
  7.         newY = [func(newX(1)), func(newX(2))];7 o3 d$ U# g" n4 C, q

  8. 9 N9 S2 d! B8 C7 m* S: w
  9.         % 找出最好的移动方向
    3 x! l! \* i5 p. x  N
  10.         [maxY, idx] = max(newY);
      Z' o7 N# f, Y1 \5 W& E& f
  11.         : [4 y, B8 ?7 N" O3 f  _
  12.         % 如果找到了更好的解，则更新当前解9 e( n+ e8 T5 W7 s
  13.         if maxY > currentY3 v  K0 \$ ~& ^9 ~) X
  14.             currentX = newX(idx);
    4 h; ^2 m1 [6 @
  15.             currentY = maxY;: F; M% D9 e7 [* V( w1 s
  16.         else* t! {, M0 |) ?6 O" }3 I% I) s
  17.             % 如果没有更好的解，结束搜索
    / U$ g! l8 H' G% E9 L/ z% t
  18.             break;
    3 [; H6 h- ?* E# {- o( l
  19.         end* b2 S: r$ V( M' g& |3 w! e
  20.     end
    + N( c$ R! N; {2 g
  21.     bestX = currentX;
    1 _* c7 w- `! `2 u9 a" C+ z
  22.     bestY = currentY;
    , U, O: U, B% S6 x- y! _
  23. end
    $ ^' @, f6 u, Y2 I) z/ j0 [

  24. . [+ Y8 m  _9 i) f) _
  25. % 运行爬山算法
    8 S- U! N9 p) V* ]
  26. initialX = 0; % 初始点
    7 Y$ U% e7 z2 k3 H' ?5 a/ s4 P
  27. stepSize = 0.1; % 步长
    & v. b/ @; E' X5 ^
  28. numIterations = 100; % 迭代次数
    9 x) W, J* F, U$ F+ @
  29. [bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);
复制代码
步骤 3: 输出结果

        展示算法找到的最优解。

  1. disp(['The maximum value of f(x) is found at x = ', num2str(bestX)]);: S( Y# d! i5 z, J1 h; _
  2. disp(['The maximum value of f(x) is ', num2str(bestY)]);
复制代码
步骤 4: 可视化

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

  1. x = 0:0.01:5;9 q: p9 ?  a$ e: |
  2. y = myFunction(x);# `4 ?3 h2 \& F) R; H( x. H" }
  3. figure;
    9 j# S5 p2 m8 N9 h: C0 ?
  4. plot(x, y, 'b-', bestX, bestY, 'ro');
    , F6 K! S9 v" r2 }: y. k1 j
  5. title('Function Optimization using Hill Climbing');
    9 j( I7 |" y1 ?# _
  6. xlabel('x');- N* T0 p) Q# Q7 v! P6 F
  7. ylabel('f(x)');
    ' F4 S( `  e) k- s
  8. legend('Function', 'Maximum Point');
复制代码

& s* w3 n% l: Q. x* M, B



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5