Genetic Network Programming (GNP) has been proposed as a new graph-based evolutionary algorithm. GNP represents its solutions as graph structures which contribute to improving the expression ability of the programs. GNP with Reinforcement Learning (GNP-RL) was also proposed as an extended algorithm of GNP and its effectiveness has been confirmed. Because GNP-RL executes reinforcement learning during task execution in addition to evolution after task execution, it can search for solutions efficiently. In this paper, GNP with Actor-Critic (GNP-AC) is proposed to enhance the effectiveness of GNP-RL. Actor-Critic can adjust numerical values appropriately during task execution, i. e., online learning, and use them for determining actions. To confirm the effectiveness of the proposed method, GNP-AC is applied to the controller of the Khepera simulator and its generalization ability is evaluated.